Minimum String Length After Removing Substrings

Minimum String Length After Removing Substrings

What is this problem about?

The Minimum String Length After Removing Substrings problem gives you a string containing only uppercase letters. You repeatedly remove occurrences of the substrings "AB" and "CD" until neither appears in the string. Find the minimum length of the resulting string. This Minimum String Length After Removing Substrings interview question is a clean application of stack-based string processing.

Why is this asked in interviews?

J.P. Morgan, Microsoft, Amazon, Google, and IBM ask this as a warm-up to assess stack intuition. It's structurally similar to bracket matching problems — a pattern that appears constantly in real-world parsers, compilers, and editors. The string, simulation, and stack interview pattern is directly tested, and candidates who reach for a stack immediately signal familiarity with string manipulation patterns.

Algorithmic pattern used

Use a stack. Traverse the string character by character. For each character, check if the top of the stack and the current character form "AB" or "CD". If they do, pop the top (removing the pair). Otherwise, push the current character. After processing the entire string, the stack's remaining characters form the minimum-length string. Its size is the answer.

Example explanation

String: "ABFCDC".

• Push 'A'.
• Push 'B' → top is 'A', pair "AB" → pop. Stack: [].
• Push 'F'. Stack: ['F'].
• Push 'C'. Stack: ['F','C'].
• Push 'D' → top is 'C', pair "CD" → pop. Stack: ['F'].
• Push 'C'. Stack: ['F','C']. Final length = 2.

Common mistakes candidates make

• Repeatedly scanning the string from scratch for "AB" or "CD" — O(n²) and unnecessary.
• Not recognizing the stack pattern (instead using string replace in loops).
• Forgetting that removing pairs can expose new pairs to remove (cascading effect handled naturally by the stack).
• Pushing the current character after an invalid check without popping.

Interview preparation tip

Any time a problem involves "remove adjacent pairs until none remain," reach for a stack. The cascading removal is automatically handled because the stack always exposes the most recently pushed character to pair with the next incoming character. This exact pattern handles bracket matching, duplicate removal, and substring elimination uniformly. Practicing 5-10 stack-based string problems will make this pattern instinctive.