Remove All Adjacent Duplicates In String
Problem
Given a string s, repeatedly remove all adjacent duplicate characters until no more duplicates remain, and return the resulting string.
- 1 ≤ s.length ≤ 10⁵
- s consists only of lowercase English letters.
Example
s = "abbaca""ca"The algorithm scans the string from left to right, using a stack to track characters. When it encounters 'a', it pushes it onto the stack. Next, it sees 'b' and pushes it. The following 'b' matches the top of the stack, so it pops the previous 'b', effectively removing the adjacent duplicates 'bb'. Then it processes 'a', which matches the top of the stack, so it pops the previous 'a'. Finally, it pushes 'c' and 'a'. The resulting stack is ['c', 'a'], which joins to form "ca".
Approach
Straightforward Solution
A naive approach would repeatedly scan the string to find adjacent duplicates and remove them, repeating until no duplicates remain. This approach can be O(n^2) in the worst case due to repeated rescanning and string rebuilding.
Core Observation
Removing adjacent duplicates repeatedly is equivalent to simulating the process with a stack: pushing characters and popping when the top matches the current character. This simulates the collapsing of duplicates in a single pass.
Path to Optimal
PreviewThe key insight is to simulate the removal process in one pass using a stack. Each character is compared to the top of the stack; if they match, the top is popped (removing the duplicate pair), otherwise the character is pushed…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a stack to process the string in a single pass. For each character, if the stack is not empty and the top equals the current character, pop the stack to remove the duplicate pair…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
Each character is pushed and popped at most once, resulting in a linear time complexity proportional to the length of the string.
Space
O(n)
The stack can hold up to all characters in the worst case (no duplicates), so auxiliary space scales linearly with input size.
Pattern Spotlight
Stack (Simulated State Reduction)
When a problem requires repeatedly removing adjacent duplicates or matching pairs, simulate the process with a stack that pushes new elements and pops when a matching pair is found, effectively reducing the problem to a single linear pass.
Solution
| 1 | class Solution:
|
| 2 | def removeDuplicates(self, s: str) -> str:
|
| 3 | stack = []
|
| 4 | for c in s:
|
| 5 | if stack and stack[-1] == c:
|
| 6 | stack.pop()
|
| 7 | else:
|
| 8 | stack.append(c)
|
| 9 |
|
| 10 | return "".join(stack) |
Step-by-Step Solution
Simulate Adjacent Duplicate Removal by Iterating and Managing Stack
| 3 | stack = []
|
| 4 | for c in s:
|
| 5 | if stack and stack[-1] == c:
|
| 6 | stack.pop()
|
| 7 | else:
|
| 8 | stack.append(c)
|
Objective
To process each character in the string, removing adjacent duplicates by pushing or popping from the stack accordingly.
Key Insight
The stack maintains the current state of the string after all removals so far. When the current character matches the top of the stack, popping simulates removing the duplicate pair immediately. Otherwise, pushing the character extends the current reduced string. This approach avoids repeated rescanning and achieves linear time complexity.
Interview Quick-Check
Core Logic
Push characters onto the stack unless the top matches the current character, in which case pop to remove the duplicate pair.
State & Boundaries
Check if the stack is non-empty before comparing to avoid errors and correctly handle the first character.
Common Pitfalls & Bugs
Forgetting to check if the stack is empty before accessing the top element can cause runtime errors.
Complexity
Each character is processed once, and each push/pop operation is O(1), resulting in O(n) time.
Construct Final String from Stack Contents
To produce the final string by concatenating the characters remaining in the stack after processing.
1 more step with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if stack and stack[-1] == c:Check if the stack is non-empty and the top character equals the current character.
This condition detects adjacent duplicates by comparing the current character with the last character in the reduced string (top of the stack), enabling immediate removal.
stack.pop()Remove the top character from the stack to eliminate the duplicate pair.
Popping the stack simulates removing the adjacent duplicate pair, effectively reducing the string state without rescanning.
Full line-by-line criticality + rationale for all 7 lines available on Pro.
Test Your Understanding
Why does using a stack guarantee that all adjacent duplicates are removed in a single pass?
See the answer with Pro.
Related Problems
Monotonic Stack pattern
Don't just read it. Drill it.
Reconstruct Remove All Adjacent Duplicates In String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove All Adjacent Duplicates In String drill