2696. Minimum String Length After Removing Substrings Easy

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.

Example 1:
Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:

• Remove the substring "AB" from "ABFCACDB", so s = "FCACDB".
• Remove the substring "CD" from "FCACDB", so s = "FCAB".
• Remove the substring "AB" from "FCAB", so s = "FC".
  So the integer 2 is returned.
  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 length remains the same.

Approach

Input: A string s containing only uppercase English letters

Output: The minimum possible string length after removing any "AB" or "CD" substrings

This problem is a typical Pair Elimination Stack problem.

We use a stack stack to simulate the character processing process:

1. Iterate through each character in the string;
2. Before pushing into the stack, check if the current character can form "AB" or "CD" with the top character of the stack:
   • If they can, pop the top of the stack and skip the current character (i.e., "eliminate a pair");
   • Otherwise, push the current character onto the stack;
3. After the traversal is complete, the remaining characters in the stack are those that cannot be further eliminated. Just return its length.

Implementation

python

class Solution:
    def minLength(self, s: str) -> int:
        stack = []

        # Iterate over each character of the string
        for c in s:
            # Check if the current character can form an eliminatable pair with the stack top
            if stack:
                top = stack[-1]
                # If we encounter 'B' and top is 'A', or we encounter 'D' and top is 'C', pair and eliminate
                if (c == 'B' and top == 'A') or (c == 'D' and top == 'C'):
                    stack.pop()
                    continue  # Current character has been eliminated, continue to the next 
            
            # Otherwise, push it directly onto the stack
            stack.append(c)

        # The number of remaining characters in the stack is the minimum possible length
        return len(stack)

javascript

/**
 * @param {string} s
 * @return {number}
 */
const minLength = function(s) {
    const stack = [];

    for (let c of s) {
        if (stack.length) {
            const top = stack.at(-1);

            if (c == 'B' && top == 'A' || c == 'D' && top == 'C') {
                stack.pop();
                continue;
            }
        }

        stack.push(c);
    }

    return stack.length;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

2696. Minimum String Length After Removing Substrings (English)

2696. 删除子串后的字符串最小长度 (Chinese)