Minimum String Length After Removing Substrings

Problem Description

Ah, the classic dilemma of string manipulation! Imagine you’re at a party, and you’ve just spilled a drink on your favorite shirt. You try to clean it up, but instead of just the drink, you accidentally remove the entire shirt! This is somewhat akin to the problem of “Minimum String Length After Removing Substrings.”

In this LeetCode challenge, you are given a string s that contains characters, and your task is to remove specific pairs of characters: ‘A’ followed by ‘B’ and ‘C’ followed by ‘D’. The goal is to determine the minimum length of the string after all possible removals. It’s like trying to tidy up your life by removing toxic relationships, but instead, you just end up with a shorter string!

Code Solution


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

        def match(c: str) -> bool:
            return stack and stack[-1] == c

        for c in s:
            if c == 'B' and match('A'):
                stack.pop()
            elif c == 'D' and match('C'):
                stack.pop()
            else:
                stack.append(c)

        return len(stack)

Approach Explanation

The approach here is quite straightforward yet clever. We utilize a stack to keep track of characters as we iterate through the string. When we encounter a ‘B’, we check if the last character in the stack is ‘A’. If it is, we pop ‘A’ off the stack, effectively removing the pair ‘AB’. The same logic applies for ‘C’ and ‘D’. If neither condition is met, we simply add the character to the stack. At the end of the iteration, the length of the stack gives us the minimum length of the string after all possible removals.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the string. We traverse the string once.
Space Complexity	O(n) in the worst case, where no characters are removed, and all characters are stored in the stack.

Real-World Example

Think of this problem like cleaning out your closet. You have a bunch of clothes (characters) that you want to keep, but every time you find a pair of shoes (like ‘A’ and ‘B’) that you don’t want together, you toss them out. After a while, you’re left with a neatly organized closet (the stack) and a clear idea of what you actually want to keep.