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 your drink on your favorite shirt. You try to clean it up, but instead of just the drink, you accidentally remove the shirt’s buttons too! Now you’re left with a shirt that’s not only wet but also buttonless. This is somewhat akin to the problem of “Minimum String Length After Removing Substrings.”

In this problem, you’re given a string s and you need to remove all occurrences of the substrings “AB” and “CD”. The goal is to find the minimum length of the string after all possible removals. It’s like trying to clean up your life by removing all the bad influences, but instead, you just end up with a shorter, messier version of yourself!

Code Solution


class Solution {
  public int minLength(String s) {
    Deque stack = new ArrayDeque<>();

    for (final char c : s.toCharArray())
      if (c == 'B' && match(stack, 'A'))
        stack.pop();
      else if (c == 'D' && match(stack, 'C'))
        stack.pop();
      else
        stack.push(c);

    return stack.size();
  }

  private boolean match(Deque stack, char c) {
    return !stack.isEmpty() && stack.peek() == c;
  }
}

Approach Explanation

The approach used in the code is quite clever. It utilizes a stack data structure to keep track of characters as they are processed. As each character is examined, the code checks if it can form a removable substring with the character at the top of the stack. If it can, it pops the top character off the stack (removing the substring). If not, it pushes the current character onto the stack. This continues until all characters have been processed, and the size of the stack at the end gives 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. Each character is processed 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

Let’s say you’re trying to clean up your social media feed. You keep seeing posts that make you cringe, like “AB” (Awkward Banter) and “CD” (Cringe-worthy Drama). Every time you see one, you try to remove it, but somehow, more keep popping up! Eventually, you realize that after all the removals, you’re left with a much shorter feed that’s actually enjoyable. This is exactly what the algorithm does with the string!