Remove All Adjacent Duplicates In String
Remove All Adjacent Duplicates In String: repeatedly delete two adjacent equal letters until no such pair remains, and return the final string.
- 1 <= s.length <= 10⁵
- s consists of lowercase English letters.
Intuition
After a deletion, the characters on either side become neighbours and may cancel in turn — so the removals cascade. A stack handles that automatically: compare each new character with the last surviving one. If they match, cancel both; otherwise push. The stack is always the answer-so-far.
Pairwise cancellation between neighbours — where a removal can trigger another removal — is the stack signature. The tell is any rule of the form 'delete two adjacent X and repeat'. The same pattern drives Valid Parentheses, Backspace String Compare, and Asteroid Collision.
Approach
Before reading on: in "abba", what happens after 'bb' disappears? Which single character do you need to compare each new letter against to catch that chain reaction? Aim for one pass.
The cascade is the whole difficulty
Naively scanning for a duplicate pair, deleting it, and restarting is correct but O(n²) — each deletion can expose a new pair further left, forcing another scan. In "abba", removing bb makes the two as adjacent, and they must go too. Any solution has to handle this chain reaction without repeatedly re-walking the string.
The stack top is the only character that matters
Process characters left to right, keeping the survivors on a stack. For each new character, the only thing it can cancel with is the most recent survivor — that is exactly the stack top. If they are equal, pop, and both vanish. If not, push. When a pop happens, the new top is whatever preceded the removed pair, which is precisely the neighbour that the deletion exposed, so the cascade is handled with no extra logic at all.
Why the stack is already the answer
At every moment the stack holds, in order, the characters that have survived all cancellations so far. Nothing below the top can be affected by future characters, because cancellation is strictly between neighbours. So when the scan ends, joining the stack bottom-to-top gives the final string directly. Each character is pushed once and popped at most once, giving O(n) time and O(n) space.
Solution & live demo
Common pitfalls
Repeatedly scanning and deleting
while True:
for i in range(len(s) - 1):
if s[i] == s[i+1]:
s = s[:i] + s[i+2:]
break
else:
breakfor ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)Correct but O(n²) — each removal restarts the scan, and on a fully cancelling input like "aabb..." that is quadratic. The stack achieves the same cascade in one pass.
Checking the stack top without a guard
if stack[-1] == ch:
if stack and stack[-1] == ch:
On the first character, or any time the stack has been fully emptied by cancellations, stack[-1] raises IndexError. The emptiness check must come first.
Comparing against the original neighbour
if i > 0 and s[i] == s[i-1]:
if stack and stack[-1] == ch:
The relevant neighbour is the last surviving character, not the one that happened to precede it in the input. In "abba", the final 'a' must be compared with the first 'a' — which is only adjacent after 'bb' is gone.
Edge cases
'bb' cancels, then the exposed 'a' meets the stacked 'a' and cancels too, leaving an empty string.
Nothing ever matches the top, so the stack is the original string.
The stack empties and the result is the empty string.
The first two cancel and the third is pushed onto an empty stack, leaving "a".
It is pushed and never matched, so it is returned unchanged.