Remove All Adjacent Duplicates In String
Last Updated: March 29, 2026
Understanding the Problem
Think of this problem like the game where you tap matching adjacent tiles and they disappear, which might cause new tiles to become adjacent and create a chain reaction. 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.
The key observation is that this chain reaction behavior, where removing a pair can create new pairs, is exactly the kind of "process something, then possibly undo or react to the result" pattern that a stack handles naturally. Instead of repeatedly scanning the entire string to find pairs (which would be slow), we can process characters one at a time and use a stack to catch pairs as they form.
Key Constraints:
1 <= s.length <= 10^5— With up to 100,000 characters, we need O(n log n) or better. An O(n^2) approach that repeatedly scans and removes pairs could be too slow in the worst case.sconsists of lowercase English letters only — No special characters. Only 26 possible character values. This simplifies comparison logic.
Approach 1: Brute Force (Repeated Scanning)
Intuition
The most straightforward interpretation of the problem: keep scanning the string for adjacent duplicates, remove the first pair you find, and repeat until no more pairs exist. This directly simulates what the problem describes.
It works, but it is inefficient. Every time we find and remove a pair, we rebuild or re-scan the string from the beginning. If the string has many nested pairs, this could take many passes.
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 here is restarting the scan from the beginning after every removal. What if we could detect and resolve pairs as we encounter them, without ever going back?
Approach 2: Stack (Optimal)
Intuition
Instead of placing all characters and then hunting for pairs, we can check for duplicates as we build the result. Process characters one at a time from left to right. Before placing a character, check if it matches the last character we placed. If it does, they form an adjacent pair, so remove the last character and skip the new one. If they don't match, place the new character.
This is classic stack behavior. The stack holds the characters that have survived so far. Each new character either cancels the top of the stack (if they match) or gets added to the stack. By the time we have processed every character, the stack contains exactly the final string.
The stack acts as a buffer that holds "what we have built so far." When we encounter a character that matches the most recent surviving character, they form an adjacent pair and both get removed. After removal, the new top of the stack is whatever was underneath the removed character, which is exactly the character that is now adjacent in the result string. So any chain reactions happen naturally, one comparison at a time, without any backtracking or rescanning.
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.