Input: s ="ABFCACDB"Output: 2Explanation: We can do the following operations:- Remove the substring "ABFCACDB", so s ="FCACDB".- Remove the substring "FCACDB", so s ="FCAB".- Remove the substring "FCAB", so s ="FC".So the resulting length of the string is2.It can be shown that it is the minimum length that we can obtain.
Example 2:
1
2
3
Input: s ="ACBBD"Output: 5Explanation: We cannot do any operations on the string so the length remains the same.
publicclassSolution {
publicintminLength(String s) {
// Initialize a stack to store characters Stack<Character> stack =new Stack<>();
// Iterate through each character in the stringfor (char c : s.toCharArray()) {
// Check if the stack is not empty and the top of the stack together with the current character forms "AB" or "CD"if (!stack.isEmpty() && ((stack.peek() =='A'&& c =='B') || (stack.peek() =='C'&& c =='D'))) {
stack.pop(); // Remove the top character from the stack (and skip the current character by not adding it to the stack) } else {
stack.push(c); // Add the current character to the stack }
}
// The size of the stack represents the length of the string after all possible removalsreturn stack.size();
}
}
1
2
3
4
5
6
7
8
9
classSolution:
defminLength(self, s: str) -> int:
stack = []
for char in s:
if stack and ((stack[-1] =='A'and char =='B') or (stack[-1] =='C'and char =='D')):
stack.pop()
else:
stack.append(char)
return len(stack)
⏰ Time complexity: O(n), where n is the length of the string s, because we process each character of the string once.
🧺 Space complexity: O(n), since in the worst case, all characters might end up in the stack.
Method 3 - Working with mutable string using two pointer technique#
Here is the approach:
Initial Setup:
Use two pointers: read and write.
Start both pointers at the beginning of the string.
Traverse the String:
Traverse the string using the read pointer.
Use the write pointer to keep track of the position where the next character should be written.
Character Check and Writing:
For each character the read pointer encounters:
If the current character and the previous character (at the write pointer’s previous position) form “AB” or “CD”, move the write pointer back by one position (effectively removing the last written character).
If they don’t form “AB” or “CD”, write the current character to the write pointer’s current position and move the write pointer forward.
End of Processing:
After processing all characters, the write pointer’s position will indicate the length of the processed string, and the characters from the start up to this position (exclusive) form the reduced string.
publicclassSolution {
publicintminLength(String s) {
// Convert the input string to a character array as strings are immutable in Javachar[] arr = s.toCharArray();
int write = 0; // Initialize the write pointer to 0// Iterate through each character in the string using the read pointerfor (int read = 0; read < s.length(); read++) {
// Assign the character at the read pointer to the position at the write pointer arr[write]= arr[read];
// Check if the current character at the write pointer along with the previous character form "AB" or "CD"if (write > 0 && ((arr[write]=='B'&& arr[write - 1]=='A') || (arr[write]=='D'&& arr[write - 1]=='C'))) {
// If they do, move the write pointer back by one to remove the previous character write--;
} else {
// If they don't, move the write pointer forward to write the new character write++;
}
}
// The write pointer's final position represents the length of the reduced stringreturn write;
}
}
classSolution:
defminLength(self, s: str) -> int:
# Convert string to a list of characters since strings are immutable arr = list(s)
write =0# Initialize the write pointer to 0# Iterate through each character in the string using the read pointerfor read in range(len(arr)):
# Assign the character at the read pointer to the position at the write pointer arr[write] = arr[read]
# Check if the current character at the write pointer along with the previous character form "AB" or "CD"if write >0and ((arr[write] =='B'and arr[write -1] =='A') or (arr[write] =='D'and arr[write -1] =='C')):
write -=1# Remove the previous character (pair formation)else:
write +=1# Move the write pointer forward to write the new character# The write pointer's final position represents the length of the reduced stringreturn write