2696. Minimum String Length After Removing Substrings

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 "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.

Constraints:

• 1 <= s.length <= 100
• s consists only of uppercase English letters.

Approach 01:

#include <iostream>
#include <stack>
#include <string>
using namespace std;

class Solution {
public:
    int minLength(string inputString) {
        stack<char> charStack;

        for (const char currentChar : inputString) {
            if (currentChar == 'B' && isMatchingPair(charStack, 'A')) {
                charStack.pop();
            } else if (currentChar == 'D' && isMatchingPair(charStack, 'C')) {
                charStack.pop();
            } else {
                charStack.push(currentChar);
            }
        }

        return charStack.size();
    }

private:
    bool isMatchingPair(const stack<char>& charStack, char comparisonChar) {
        return !charStack.empty() && charStack.top() == comparisonChar;
    }
};

class Solution:
    def minLength(self, inputString):
        charStack = []

        for currentChar in inputString:
            if currentChar == 'B' and self.isMatchingPair(charStack, 'A'):
                charStack.pop()
            elif currentChar == 'D' and self.isMatchingPair(charStack, 'C'):
                charStack.pop()
            else:
                charStack.append(currentChar)

        return len(charStack)

    def isMatchingPair(self, charStack, comparisonChar):
        return charStack and charStack[-1] == comparisonChar

Time Complexity

• Iterating through the input string:The function iterates through each character in the input string exactly once, which takes \(O(n)\), where \(n\) is the length of the input string.
• Stack operations:Each character is either pushed onto the stack or popped from the stack at most once. Both push and pop operations on the stack are \(O(1)\). Thus, the overall time complexity remains \(O(n)\).
• Overall Time Complexity:The overall time complexity is \(O(n)\), where \(n\) is the length of the input string.

Space Complexity

• Auxiliary Space:The space complexity is determined by the maximum size of the stack. In the worst case, when no matching pairs are found, the stack could hold all characters of the input string. Thus, the space complexity is \(O(n)\).
• Overall Space Complexity:The overall space complexity is \(O(n)\), where \(n\) is the length of the input string.