Remove All Adjacent Duplicates in String
Keep deleting pairs of equal neighboring letters until none are left. The simplest use of a stack to handle chain reactions in one pass. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string s of lowercase letters. A removal deletes two adjacent characters that are the same letter, and the parts on either side join together.
Keep making removals until no two neighbors match, then return the final string. The result doesn't depend on which pair you remove first, so there is exactly one correct answer.
Example 1
- Input
- s = "xyyxz"
- Output
- "z"
Removing "yy" leaves "xxz". Now the two xs touch, and removing them leaves "z".
Example 2
- Input
- s = "cabbad"
- Output
- "cd"
"bb" goes first, then "aa", leaving "cd".
Example 3
- Input
- s = "abc"
- Output
- "abc"
No neighbors match, so nothing changes.
Constraints
- 1 ≤ s.length ≤ 10⁵
- s contains only lowercase English letters.
- The answer may be the empty string.
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Remove All Adjacent Duplicates in String in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Remove All Adjacent Duplicates in String
Pattern: Stack as the surviving prefix
When a pair is removed, the characters on either side become neighbors and might form a new pair. That chain reaction looks like it needs repeated passes, but it doesn't if you think of the answer as being built left to right.
Keep a stack of the characters that have survived so far. For each new character, if it matches the top of the stack, the two cancel: pop. Otherwise push it. Popping exposes the previous survivor, which is exactly the character that becomes the new neighbor, so chain reactions resolve on their own. At the end, the stack (bottom to top) is the answer.
Approach 1: Rescan until nothing changes
Find the first pair of equal neighbors, cut it out, and scan again from the start. Stop when a pass finds nothing. Correct, but a string like "abccba" needs a pass per pair, and each pass copies the string.
Time O(n²) · Space O(n)
Approach 2: Stack of characters
- Start with an empty stack.
- For each character
c: if the stack's top isc, pop it; otherwise pushc. - Join the stack into a string.
Each character is pushed at most once and popped at most once.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Rescan until nothing changes | O(n²) | O(n) |
| Stack of characters | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Remove All Adjacent Duplicates in String solution in Python
def remove_duplicates(s: str) -> str:
stack = []
for ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
return "".join(stack)Remove All Adjacent Duplicates in String solution in JavaScript
function removeDuplicates(s) {
const stack = [];
for (const ch of s) {
if (stack.length && stack[stack.length - 1] === ch) stack.pop();
else stack.push(ch);
}
return stack.join('');
}Common mistakes
- Doing a single pass that only removes pairs present in the original string and missing the ones that form afterward.
- Removing all of a run of three like "aaa". Only pairs cancel, so one a remains.
- Building the result with repeated string concatenation or slicing, which can turn a linear algorithm quadratic.
- Reading the top of an empty stack without checking it first.
What interviewers look for
Name the pattern quickly: "matching neighbors cancel, which is a stack, like matching parentheses." Then trace "xyyxz" to show that popping y exposes x for the next character to cancel.
If asked about space, mention that you can use the output buffer itself as the stack, so the only extra memory is the answer.
Follow-up questions
What if you need to remove runs of k equal characters instead of pairs?
Store a count with each stack entry: increment it when the next character matches the top, and pop the entry when the count reaches k. It stays O(n).
Can you do it in place?
Yes, with a write pointer over a character array. For each read position, copy the character to s[write]; if write > 0 and s[write - 1] equals it, decrement write instead of advancing. The first write characters are the answer.
Why is the answer unique regardless of removal order?
Each letter behaves like an element that cancels itself, so the process is like reducing a word in a group where every letter is its own inverse. Any sequence of cancellations reaches the same fully reduced word, which the stack computes directly.
Companies that ask Remove All Adjacent Duplicates in String
Remove All Adjacent Duplicates in String is tagged by 93 companies in our interview dataset. The score shows how often it comes up at each company.
- Getyourguide100%
- NTT100%
- Urban100%
- Miro100%
- Ancestry96%
- Whatnot95.6%
- Paytm94.3%
- Quinto Andar93%
- Grammarly91.8%
- Iterable90%
- Abbvie88%
- Springworks Therapeutics84%
- AT&T84%
- Encora81%
- Endava81%
- GE Aerospace81%
- Clevertap80%
- Surveymonkey80%
- Elastic79%
- Relativity Space79%
- Hbc Digital78%
- Genentech78%
- Acquia78%
- Solventum78%
and 69 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required