Remove All Adjacent Duplicates In String
Easy · Stack & Strings · String · Stack
Problem
You are given a string s of lowercase letters. A removal step picks two adjacent, equal letters and deletes both of them.
Keep applying removal steps until none is possible, and return the final string. The result is the same whichever pairs you remove first, so the answer is unique.
Examples
Input: s = "xyyxz" Output: "z"
Removing "yy" leaves "xxz", and removing "xx" then leaves "z".
Input: s = "aab" Output: "b"
The pair "aa" is removed and "b" remains.
Input: s = "abba" Output: ""
"bb" goes first, which makes "aa" adjacent, and it goes too.
Constraints
- 1 <= len(s) <= 10^5
- s consists of lowercase English letters
Approaches
- Baseline: remove one pair at a time, rescan — time O(n²), space O(n)
Follow-up
What if a removal needs k equal adjacent letters instead of two? Store (letter, run length) pairs on the stack and pop when a run reaches k. And if two letters cancel when they are the same letter in different cases ("aA")? Only the comparison with the top changes.
Related problems
Start free on Cariara · Coding problems · System design studio
