Remove All Adjacent Duplicates In String: Stack Pattern
You are given a string and told to repeatedly remove adjacent duplicate characters until none remain. This is LeetCode 1047: Remove All Adjacent Duplicates In String, rated easy. A stack makes this a single-pass problem.
The problem
Given a string s, repeatedly remove two adjacent characters that are the same until no more adjacent duplicates exist. Return the final string.
Input: "abbaca"
Output: "ca"
The removals happen like this: "abbaca" becomes "aaca" (remove "bb"), then "aaca" becomes "ca" (remove "aa"). You keep going until no adjacent pair is left.
Input: "azxxzy"
Output: "ay"
Here "azxxzy" becomes "azzy" (remove "xx"), then "azzy" becomes "ay" (remove "zz"). Notice how removing one pair can create a new adjacent pair that also needs to be removed.
Why a stack works
The tricky part is that removing one pair of duplicates can expose a new pair. If you try to scan the string and remove pairs one at a time, you end up making multiple passes. That is slow and messy.
A stack handles this naturally. Walk through the string character by character. For each character, compare it to the top of the stack. If they match, pop the top (this removes the adjacent pair). If they do not match, push the current character. By the time you reach the end of the string, the stack contains the final result with all adjacent duplicates removed, in a single pass.
The key insight is that the stack always holds the "processed so far" portion of the string. When a new character matches the top, it means the new character and the previous character are adjacent duplicates, so they cancel each other out. This cascading cancellation is exactly what the problem asks for.
The solution
def removeDuplicates(s: str) -> str:
stack = []
for ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
return ''.join(stack)
Here is what each part does:
stack = []: This list acts as our stack. It will hold the characters of the result as we build it.for ch in s: We walk through the input string one character at a time.if stack and stack[-1] == ch: Check two things. First, is the stack non-empty? Second, does the character on top match the current character? If both are true, we have found an adjacent duplicate.stack.pop(): Remove the top character. Both the top and the current character are duplicates, so neither makes it into the result.stack.append(ch): If there is no match (or the stack is empty), push the current character. It becomes the new top, waiting to see if the next character will match it.''.join(stack): After processing every character, whatever remains in the stack is the answer. Join it into a string.
This is the same pattern used in matching parentheses: push when you see an "opener," pop when you see a "closer" that matches the top. Here, every character is both an opener and a potential closer for the character before it.
Visual walkthrough
Let's trace through "abbaca" step by step. Watch how the stack grows when characters do not match and shrinks when adjacent duplicates are found.
Step 1: Read "a" (index 0). Stack is empty, push "a".
Nothing to compare against. Push "a" onto the stack.
Step 2: Read "b" (index 1). Top is "a", no match. Push "b".
"b" does not equal "a" (the top of the stack), so we push "b".
Step 3: Read "b" (index 2). Top is "b", match! Pop the top.
"b" equals the top of the stack. This is an adjacent duplicate. Pop the "b" off.
Step 4: Read "a" (index 3). Top is "a", match! Pop the top.
"a" equals the top of the stack. Pop it. The stack is now empty.
Step 5: Read "c" (index 4). Stack is empty, push "c".
Stack is empty, so we push "c" with nothing to compare.
Step 6: Read "a" (index 5). Top is "c", no match. Push "a".
"a" does not equal "c". Push "a". All characters processed. Stack holds "ca", which is the answer.
After processing all six characters, the stack contains ["c", "a"]. Joining gives "ca", which is the answer. The entire string was processed in a single left-to-right pass.
Complexity analysis
| Aspect | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Time: Each character is pushed onto the stack at most once and popped at most once. That gives us at most 2n stack operations total, which is O(n).
Space: In the worst case, the string has no adjacent duplicates at all (like "abcdef"), and every character stays on the stack. So the stack can grow up to size n.
The building blocks
Stack as a running result
The core pattern here is using a stack to build a result incrementally. Instead of constructing the output after the fact, the stack is the output at every point during the traversal. Each new character either extends the result (push) or cancels the previous character (pop). This "stack as accumulator" pattern appears whenever you need to process a sequence with potential cancellations.
stack = []
for ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
Adjacent pair cancellation
The specific check stack[-1] == ch implements pair cancellation. Two identical adjacent elements destroy each other. This is a restricted version of the bracket-matching pattern, where instead of matching specific openers to closers, any two identical neighbors cancel out. The same idea generalizes to problems where you remove groups of k consecutive duplicates (LeetCode 1209) by tracking counts alongside characters on the stack.
if stack and stack[-1] == ch:
stack.pop()
Edge cases
- No duplicates at all:
"abcdef"has no adjacent pairs. Every character is pushed and nothing is ever popped. The stack returns the original string unchanged. - Entire string cancels out:
"aabbcc"removes"aa","bb", and"cc". Each pair cancels, leaving an empty stack. The result is"". - Single character:
"a"is pushed and never matched. The result is"a". - Cascading removals:
"abba"first removes the inner"bb", leaving"aa"on the stack. Then the next"a"matches the"a"already on the stack, so that pair is also removed. The result is"". The stack handles cascading removals automatically because each pop can expose a new match. - Already minimal string:
"aba"has no adjacent duplicates. Every character is different from its neighbor. The result is"aba"unchanged.
From understanding to recall
The solution to this problem is short. Five lines of real logic. That makes it tempting to think you will always remember it. But under interview pressure, even small details trip people up. Do you check stack[-1] == ch or ch == stack[-1]? Do you pop before or after comparing? Do you need to handle the empty stack case separately?
These details become automatic with spaced repetition. Write the solution from scratch, wait a day, write it again. After a few cycles, the push-or-pop decision flows without hesitation. The pattern locks into long-term memory, and you can apply it instantly to variations like removing k consecutive duplicates or processing nested structures.
Related posts
- Valid Parentheses - The classic stack matching problem where you push openers and pop on matching closers
- Daily Temperatures - A monotonic stack problem that uses the same push/pop structure to find next-greater elements
- Backspace String Compare - Stack-based string processing where
#characters cancel previous characters, similar to how duplicates cancel here
The stack is one of the most versatile tools in your algorithm toolkit. Once the push-or-pop pattern becomes second nature, problems like this take seconds to solve, not minutes.