Remove All Adjacent Duplicates In String

Remove All Adjacent Duplicates In String

What is this problem about?

The Remove All Adjacent Duplicates In String problem repeatedly removes adjacent duplicate pairs until none remain. This easy coding problem uses a stack to efficiently process the string in one pass. The string and stack interview pattern is the most fundamental stack application.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it's the canonical "stack-based string reduction" problem — a pattern appearing in expression evaluation, text processing, and compiler design.

Algorithmic pattern used

Stack. For each character: if stack is non-empty and stack top equals current character, pop (remove the pair). Else push current character. The remaining stack characters form the result.

Example explanation

s="abbaca". Process:

• 'a': stack=['a'].
• 'b': stack=['a','b'].
• 'b': top='b'=='b' → pop. stack=['a'].
• 'a': top='a'=='a' → pop. stack=[].
• 'c': stack=['c'].
• 'a': stack=['c','a']. Result: "ca".

Common mistakes candidates make

• Using string concatenation repeatedly (O(n²)).
• Not recognizing that remaining stack characters are the answer.
• Applying multiple passes instead of single stack pass.
• Off-by-one in checking stack non-emptiness.

Interview preparation tip

Stack for adjacent duplicate removal is a foundational pattern. The stack-top comparison in one pass is O(n) and elegant. This exact pattern extends to: Remove All Adjacent Duplicates II (k duplicates), "decode strings," and "basic calculator." Master this single-pass stack approach — it's the gateway to all stack-based string processing problems.