Remove All Adjacent Duplicates in String II
Repeatedly delete any block of k identical adjacent characters until none remain. A stack problem where each entry carries a running count. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string s and an integer k. A removal picks k adjacent characters that are all the same letter and deletes them, joining the pieces on either side.
Keep making removals until no block of k equal adjacent characters is left, then return the final string. The final string is always the same no matter which block you remove first, so there is exactly one correct answer.
Example 1
- Input
- s = "abbbaac", k = 3
- Output
- "c"
Removing "bbb" leaves "aaac". That creates a new block "aaa", and removing it leaves "c".
Example 2
- Input
- s = "mnop", k = 2
- Output
- "mnop"
No two neighbors match, so nothing is removed.
Example 3
- Input
- s = "ddcccdbb", k = 2
- Output
- "cd"
Remove "dd", one pair of "cc" and "bb". The leftover single "c" and "d" never form a pair.
Constraints
- 1 ≤ s.length ≤ 10⁵
- 2 ≤ k ≤ 10⁴
- s contains only lowercase English letters.
Practice
Runs 14 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 II 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 II
Pattern: Stack of (character, run length)
Removing a block can make the characters on either side touch, which may create a new block. Scanning the string over and over handles that, but it's slow. The better view: process characters left to right and keep only what has survived so far on a stack.
The only thing that matters about the top of the stack is which letter it is and how many copies of it are in a row. So store pairs [char, count]. When the next character matches the top, bump the count; when the count reaches k, pop the whole run. Popping automatically exposes the previous run, so any chain reaction is handled for free as later characters arrive.
Approach 1: Rescan until stable
Scan the string for any run of k equal characters, cut it out, and start over. Stop when a full scan makes no change. Easy to reason about, but every removal costs a full pass and a string copy, so deeply nested inputs take quadratic time.
Time O(n² / k) · Space O(n)
Approach 2: Character stack with a separate count array
Push characters onto a stack and keep a parallel array where counts[i] is the run length ending at stack position i. When a count hits k, pop k characters. Linear, but pops cost k each and the bookkeeping is easy to get wrong.
Time O(n) · Space O(n)
Approach 3: Stack of run-length pairs
- For each character
c: if the stack top has letterc, increment its count; otherwise push[c, 1]. - If the top count is now
k, pop it. - At the end, expand each pair into
char * countand join.
Each character is pushed or counted once and each run is popped at most once.
Time O(n) · Space O(n)
| Approach | Time | Space |
|---|---|---|
| Rescan until stable | O(n² / k) | O(n) |
| Character stack with a separate count array | O(n) | O(n) |
| Stack of run-length pairs | O(n) | O(n) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Remove All Adjacent Duplicates in String II solution in Python
def remove_duplicates(s: str, k: int) -> str:
stack = [] # [char, run length]
for ch in s:
if stack and stack[-1][0] == ch:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
else:
stack.append([ch, 1])
return "".join(ch * count for ch, count in stack)Remove All Adjacent Duplicates in String II solution in JavaScript
function removeDuplicates(s, k) {
const stack = []; // [char, run length]
for (const ch of s) {
const top = stack[stack.length - 1];
if (top && top[0] === ch) {
top[1]++;
if (top[1] === k) stack.pop();
} else {
stack.push([ch, 1]);
}
}
return stack.map(([ch, count]) => ch.repeat(count)).join('');
}Common mistakes
- Removing only the blocks present in the original string and missing the new blocks that form after a removal.
- Resetting the count to zero after a pop instead of resuming the count of the run underneath.
- Building the answer with repeated string concatenation inside a loop, which can be quadratic in some languages.
- Popping when the count goes above k instead of exactly at k. A run of exactly k must disappear as soon as it forms.
What interviewers look for
Start by explaining why rescanning is slow: a removal can expose a new block, and in the worst case each pass removes only one layer. Then say the key idea in one line: "the stack holds what survives, and each entry knows how long its run is."
Walk through a chain reaction like "abbbaac" with k = 3 on the stack to show the a run resumes its count after bbb is popped. That example is the one interviewers want to see you handle.
Follow-up questions
Why is the result the same regardless of which block you remove first?
Removals behave like cancellation in a stack: the left-to-right stack process gives one canonical result, and any removal you could make by hand is also made, in some order, by the stack. Different orders reach the same fully reduced string.
Can you do it in place without a separate stack?
Yes. Use the character array itself as the stack with a write pointer, and keep a count array indexed by write position. Writing `s[write] = s[read]` and backing `write` up by `k` when the count hits `k` gives O(1) extra space beyond the counts.
What if a block of k or more should be removed, not exactly k?
You can no longer pop as soon as the count reaches k, because more copies might follow. Wait until a different character arrives (or the input ends), then pop the run if its count is at least k. The run underneath may then merge with the incoming character.
Companies that ask Remove All Adjacent Duplicates in String II
Remove All Adjacent Duplicates in String II is tagged by 89 companies in our interview dataset. The score shows how often it comes up at each company.
- Peraton100%
- Disney100%
- Attentive100%
- Factset97.2%
- Storyblocks96%
- Personio95%
- Thought Machine94%
- Alation92%
- Crispr Therapeutics88%
- Grammarly87.7%
- Agoda81.2%
- Fico81%
- Telus81%
- Highradius80%
- Trellix79%
- Blue Yonder79%
- Ntt Data79%
- Fynd79%
- Ford Motor76%
- Alten75%
- Sourcegraph74%
- Epic Games74%
- Xilinx74%
- Palantir73%
and 65 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