Remove All Adjacent Duplicates In String
The key idea
Scan left to right and keep a stack of surviving characters. Each new character either cancels the character on top of the stack (when they are equal, pop it) or is pushed on. Because a removal can expose a fresh pair, the stack handles the chain reaction automatically in a single pass.
Problem
You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.
Repeatedly make duplicate removals on s until no more can be made. Return the final string after all such removals have been made. It can be proven that the answer is unique.
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
Examples
Input: s = "abbaca"
Output: "ca"
Input: s = "azxxzy"
Output: "ay"
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Stack / Queue problems
- Asteroid CollisionMEDIUM
- Baseball GameEASY
- Basic CalculatorHARD
- Decode StringMEDIUM
- Evaluate Reverse Polish NotationMEDIUM
- Longest Valid ParenthesesHARD
- Min StackMEDIUM
- Number of Recent CallsEASY
- Removing Stars From a StringMEDIUM
- Simplify PathMEDIUM
- Valid ParenthesesEASY