Remove All Adjacent Duplicates in String
Repeatedly remove adjacent equal letters in one pass with a stack: a letter equal to the top cancels it, otherwise it is kept.
Problem Understanding
Remove All Adjacent Duplicates in String: repeatedly pick two adjacent equal letters in s and remove them, until no such pair is left. Return the final string, which is guaranteed to be unique.
Example: "abbaca" returns "ca". Removing bb gives "aaca", then removing aa gives "ca".
The Intuition: Cancel With the Top
Removing pairs over and over and rescanning is O(n²). The trick is that a removal only ever creates a new pair at the same spot. Keep the letters that survive on a stack:
- If the current letter equals the top, the two are adjacent and cancel: pop.
- Otherwise, push it.
A pop exposes the letter before the pair, which is exactly the neighbour the next letter would meet. It is the same matching idea as Valid Parentheses, where the "pair" is an opening and closing bracket instead of two equal letters.
Interactive Walkthrough
The string is on top with the current letter filled; the kept letters are below. A cancelled letter turns red for one step. Try All cancel to watch each pop expose the twin of the next letter.
Dry Run Table
Input: s = "abbaca"
| Letter | Top before | Action | Stack after |
|---|---|---|---|
| a | — | push | a |
| b | a | push | ab |
| b | b | pop | a |
| a | a | pop | (empty) |
| c | — | push | c |
| a | c | push | ca |
Answer: "ca".
The Solution Template
One stack, one comparison per letter. The C version reuses s as the stack, writing in place.
Remove All Adjacent Duplicates in String Code
1var removeDuplicates = function(s) {2 const stack = [];3 for (const c of s) {4 if (stack.length && stack[stack.length - 1] === c) stack.pop();5 else stack.push(c);6 }7 return stack.join('');8};
Edge Cases & Common Mistakes
- Chains:
"azxxzy"removesxx, which makeszzadjacent; the stack handles it without rescanning. - Odd runs:
"aaa"leaves"a"; letters cancel in pairs only. - Everything cancels: the answer can be the empty string.
- Rescanning in a loop: repeatedly searching for a pair and rebuilding the string is O(n²) and times out on long inputs.
- String concatenation in Java: building with
+=is quadratic; useStringBuilderas the stack.
Summary
Walk the string with a stack: pop when the letter equals the top, push otherwise. The stack, bottom to top, is the final string. O(n) time, O(n) space, or O(1) extra by writing in place.
More practice: DSA interview questions with answers · patterns cheat sheet