Remove All Adjacent Duplicates In String
Understanding the Problem
We have a string of lowercase letters, and whenever two identical letters sit next to each other, we remove both of them. After removing a pair, the letters that were on either side of the removed pair become new neighbors, and they might form a new duplicate pair themselves. So one removal can trigger a chain of further removals.
This "remove a pair, then react to the new neighbors" behavior maps onto a stack. As we read the string left to right, the stack holds the characters that have survived so far. A new character either cancels the most recent survivor (if they are equal) or joins it. That lets us resolve every pair in a single pass instead of repeatedly rescanning the string.
Key Constraints:
1 <= s.length <= 10^5: with up to 100,000 characters, an O(n^2) approach that rescans the whole string after each removal does roughly 5 billion operations in the worst case, which is too slow. We want a single-pass O(n) solution.sconsists of lowercase English letters only. There are no special characters to handle, and equality of two characters is a single comparison.
Approach 1: Brute Force (Repeated Scanning)
Intuition
Simulate exactly what the problem describes: scan the string for an adjacent duplicate, remove the first pair found, and repeat until no pair remains.
This is correct but inefficient. Every removal restarts the scan from the beginning, because deleting a pair can create a new pair just before the deletion point. A string of nested pairs like "aabb...zz" forces one full scan per removal.
Algorithm
- Convert the string to a mutable structure (like a StringBuilder or list).
- Scan from left to right looking for an index where
s[i] == s[i+1]. - If found, remove both characters at indices
iandi+1. - Restart the scan from the beginning (because removal may have created new adjacent duplicates).
- When a full scan finds no adjacent duplicates, return the result.
Example Walkthrough
Code
- Time Complexity: O(n^2). In the worst case, each pass removes one pair and scans the entire remaining string. With n/2 passes of up to n characters each, total work is O(n^2).
- Space Complexity: O(n). We store a mutable copy of the string, which is at most n characters long.
The bottleneck is restarting the scan from the beginning after every removal. The next approach resolves each pair the moment it forms, in a single left-to-right pass.
Approach 2: Stack (Optimal)
Intuition
Check for duplicates as we build the result instead of hunting for them afterward. Process characters left to right. Before placing a character, compare it to the last character already placed. If they are equal, they form an adjacent pair, so remove the placed character and discard the new one. Otherwise, place the new character.
The stack holds the characters that have survived so far. Each new character either cancels the top of the stack or gets pushed onto it. After processing every character, the stack contains the final string.
The reason a single left-to-right pass catches every removal, including chained ones, is the invariant: the stack never contains two equal adjacent characters. When a pop happens, the new top is whatever sat beneath the removed character, which is now adjacent to the next character we process. If those two are equal, the very next comparison removes them too. A character once popped is gone for good, so no removal can be missed and none needs revisiting.
Algorithm
- Initialize an empty stack (we will use a StringBuilder or list as a stack for efficiency).
- For each character
cin the string: - If the stack is not empty and the top element equals
c, pop the top element (the pair cancels out). - Otherwise, push
conto the stack. - Convert the stack to a string and return it.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the string once. Each character is pushed at most once and popped at most once, so the total number of stack operations is at most 2n.
- Space Complexity: O(n). In the worst case, no characters get removed (e.g., "abcdef" with no adjacent duplicates), and the stack holds all n characters.