Problem

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

Examples

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: 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 is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

Solution

Video explanation

Here is the video explaining all the methods below in detail. Please check it out:

Method 1 - Naive

The naive idea is to iteratively search for “AB” or “CD” in the string s.

  • Every time we find such a substring, we remove it and start over.
  • This process continues until no more “AB” or “CD” can be found in the string.

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Stack

  1. We need to repeatedly remove substrings “AB” or “CD” from the string s until no such substrings can be found.
  2. Whenever a substring is removed, the string might concatenate in such a way that new occurrences of “AB” or “CD” could be formed.
  3. The process should continue until no more “AB” or “CD” substrings are present in s.

Code

Java
public class Solution {
    public int minLength(String s) {
        // Initialize a stack to store characters
        Stack<Character> stack = new Stack<>();
        
        // Iterate through each character in the string
        for (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 removals
        return stack.size();
    }
}
Python
class Solution:
    def minLength(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)

Complexity

  • ⏰ 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:

  1. Initial Setup:
    • Use two pointers: read and write.
    • Start both pointers at the beginning of the string.
  2. 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.
  3. 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.
  4. 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.

Code

Java
public class Solution {
    public int minLength(String s) {
        // Convert the input string to a character array as strings are immutable in Java
        char[] arr = s.toCharArray();
        int write = 0; // Initialize the write pointer to 0
        
        // Iterate through each character in the string using the read pointer
        for (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 string
        return write;
    }

}
Python
class Solution:
    def minLength(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 pointer
        for 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 > 0 and ((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 string
        return write

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) for programming languages like Java/Python which support immutable strings
    • O(1) for languages like c/c++ which support mutable string