Remove All Adjacent Duplicates In String
Remove All Adjacent Duplicates In String is LeetCode 1047 (Easy). A duplicate removal deletes two equal letters that sit next to each other. Keep doing this on s until no such pair is left, and return the final string.
One removal can create a new pair: in "abba", deleting "bb" brings the two as together, and they must be removed too. s holds up to 10^5 lowercase letters.
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Intuition
Read the letters left to right and keep the ones that have survived so far. A new letter can only pair with the last surviving letter: every earlier survivor already has a different letter right after it.
That is a stack. If the new letter equals the top, pop the top; otherwise push the new letter. Popping exposes the letter underneath, so the next letter is compared with it, and a pair created by a removal is caught right away. Each letter is pushed once and popped at most once, so the whole string is handled in one pass.
This is the cancellation pattern: "delete neighbouring pairs and repeat, where a deletion can create a new pair". Valid Parentheses, Backspace String Compare and Asteroid Collision all compare each new item with the top of a stack in the same way.
Approach
Before reading on, take "abba" and decide which single letter the last a should be compared with after "bb" is gone. Then pick a structure that always hands you that letter in O(1). Aim for one pass.
Start with an empty stack
The stack holds the letters that survive so far, in their original order. A Python list or a C++ string works, since both add and remove at the end in O(1).
Compare each letter with the top
For each ch in s, look at the top of the stack. Check that the stack is not empty first; after a full cancellation, or on the first letter, there is no top to read.
Pop on a match, push otherwise
If ch equals the top, pop it and drop ch: the two cancel. Otherwise push ch; a later letter may still cancel it.
Join the stack
When every letter is read, the stack from bottom to top is the answer. It is already in input order, so join it into a string without reversing.
Remove All Adjacent Duplicates In String solution in Python | C++ | Java
Common pitfalls
Comparing with the previous input letter
for i in range(1, len(s)):
if s[i] == s[i - 1]:
...for ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)The previous letter in s may already be gone. In "abba" the last a has to be compared with the first a, which only becomes its neighbour once "bb" is removed. A single scan of s[i - 1] returns "aa" instead of "".
Deleting from the string and starting over
while True:
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
s = s[:i] + s[i + 2:]
break
else:
return sstack = []
for ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
return "".join(stack)It gives the right answer, but each removal copies the string and restarts the scan. On "ab" * 25000 + "ba" * 25000 that is 50,000 removals over a string of up to 100,000 letters, which is far too slow.
Complexity
s. Each letter is pushed once and popped at most once. The stack can hold all n letters when nothing cancels, as in "abc".Adjacent duplicate problems
Three problems remove neighbouring repeats, but they remove different amounts, so the same input can come out differently.
| Problem | Removes | "aaa" becomes |
|---|---|---|
| 1047 Remove All Adjacent Duplicates In String (this page) | two equal neighbours at a time | "a" |
| 1209 Remove All Adjacent Duplicates in String II | k equal neighbours at a time; the stack stores each letter with its run count | "" when k = 3 |
| Recursively Remove Adjacent Duplicates | every whole run of two or more equal letters | "" |
Remove All Adjacent Duplicates In String FAQ
Why does the order of removals not change the answer?
Take any two pairs you could remove right now. If they sit apart, removing one leaves the other in place, so you can do both in either order. If they overlap, as in "aaa", removing either one leaves the same "a". So two different first choices can always be brought back to the same string, and every route ends at the one result the stack builds.
Can it be done without an extra stack?
Yes. Use the string's own array as the stack: keep a write index top, copy each letter to chars[top], and step top back by one instead of popping when the letter matches chars[top - 1]. The answer is chars[:top]. It is the same algorithm with O(1) extra space in languages with mutable strings.