Minimum String Length After Balanced Removals

medium string stack counting

Problem

You are given a string s of only 'a' and 'b'. You may repeatedly remove any substring that contains an equal number of 'a' and 'b' characters; the surrounding parts then join together. Return the minimum possible length after any number of such removals.

Because an 'a' and a 'b' together form a balanced (removable) pair, every pairing can be cancelled. Process the characters with a stack: if the current character is the opposite of the stack's top, pop it (cancel a pair); otherwise push. What survives is just the surplus of whichever letter is more common, so the answer equals abs(count_a − count_b).

Inputs = "aaabb"

Output1

Remove "ab" to get "aab", remove "ab" again to get "a". One leftover 'a' remains, so the length is 1.

s (only 'a' and 'b')

def minLengthAfterRemovals(s):
    stack = []
    for ch in s:
        if stack and stack[-1] != ch:
            stack.pop()          # cancel a balanced a-b pair
        else:
            stack.append(ch)     # nothing to cancel; keep it
    return len(stack)            # == abs(count_a - count_b)

function minLengthAfterRemovals(s) {
  const stack = [];
  for (const ch of s) {
    if (stack.length && stack[stack.length - 1] !== ch) {
      stack.pop();               // cancel a balanced a-b pair
    } else {
      stack.push(ch);            // nothing to cancel; keep it
    }
  }
  return stack.length;           // == abs(countA - countB)
}

int minLengthAfterRemovals(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char ch : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek() != ch) {
            stack.pop();         // cancel a balanced a-b pair
        } else {
            stack.push(ch);      // nothing to cancel; keep it
        }
    }
    return stack.size();         // == abs(countA - countB)
}

int minLengthAfterRemovals(string s) {
    vector<char> stack;
    for (char ch : s) {
        if (!stack.empty() && stack.back() != ch) {
            stack.pop_back();    // cancel a balanced a-b pair
        } else {
            stack.push_back(ch); // nothing to cancel; keep it
        }
    }
    return (int)stack.size();    // == abs(countA - countB)
}

Explanation

The trick is realising that the order of removals does not matter. A removable substring needs equal counts of 'a' and 'b', and the smallest such unit is a single 'a' next to a single 'b'. Any 'a' can ultimately be matched with any 'b', so the only characters that can never disappear are the surplus of whichever letter is more frequent.

A stack turns this insight into a single left-to-right pass. We keep unmatched characters on the stack. For each new character ch, we look at the top of the stack: if it is the opposite letter, the two cancel as a balanced pair, so we pop. Otherwise there is nothing to pair with, so we push ch onto the stack.

Because the top of the stack is always the most recent unmatched character, this greedy cancellation never traps a pair that could have been removed. After the pass, the stack holds only leftover characters that are all the same letter — exactly the surplus.

So the final answer is the stack's size, which equals abs(count_a − count_b). You could skip the stack entirely and just count letters, but the stack makes the cancellation visible step by step, which is what the visualizer above animates.

Example: s = "aaabb". Push a, a, a; then b cancels a top a (pop), and the next b cancels another a (pop). One a remains, so the minimum length is 1.

Time: O(n) Space: O(n)