Problem Statement

Remove All Adjacent Duplicates in String II

You get a string s and a number k. The rule is simple: any time you see k of the same letter sitting right next to each other, you delete all k of them. You keep doing this until there are no more groups of k matching letters in a row. Return whatever is left. The slow way is to scan the whole string over and over, deleting a group and starting again. The smart way uses a tool called a stack. A stack is like a pile of plates: you only add to the top and only take from the top, so the last plate you put on is the first one you take off (this is called last in, first out). Here we put each letter on the pile along with a count of how many of that same letter are stacked up at the top. When that count hits k, we lift that whole group off the pile. The nice part is that lifting a group off can leave two older groups touching, and the stack handles that for us automatically because they were already sitting there as separate entries.

mediumStackStackTime: O(n) · Space: O(n)

Signals to notice

remove adjacent groups of k identical charactersgeneralized from pairs to groups of kstack with counts

Brute force first

Repeatedly scan and remove — O(n²/k).

The key insight

Stack of (char, count). Push chars, increment if same as top. When count = k, pop. O(n).

Trace it on `s="deeedbbcccbdaa", k=3`

ch='d': push -> [[d,1]]
ch='e','e','e': count hits 3 -> pop -> [[d,1]]
ch='d': top is d, count++ -> [[d,2]]; then 'b','b' -> [[d,2],[b,2]]
ch='c','c','c': count hits 3 -> pop -> [[d,2],[b,2]]
ch='b': top is b, count++ -> [b,3] hits k -> pop -> [[d,2]]
ch='d': top is d, count++ -> [d,3] hits k -> pop -> []
ch='a','a': push then count++ -> [[a,2]]
End: join chars -> 'aa' (returned)

What must stay true

The (char, count) stack tracks consecutive identical characters. Removal at k automatically exposes new adjacencies.

Shape of the loop

stack = []                       # entries are [char, count]
for ch in s:
    if stack and stack[-1].char == ch: stack[-1].count += 1
    else: stack.push([ch, 1])
    if stack[-1].count == k: stack.pop()
return concat(ch repeated count for [ch,count] in stack)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not tracking counts — plain char stack requires recounting after each removal.

Stack Pattern