Remove All Adjacent Duplicates in String II

Remove All Adjacent Duplicates in String II

What is this problem about?

The Remove All Adjacent Duplicates in String II problem removes groups of k consecutive identical characters repeatedly until no more groups of k exist. This medium coding problem uses a stack storing (character, count) pairs to efficiently track runs. The string and stack interview pattern is demonstrated at an intermediate level.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, TikTok, Google, Bloomberg, and others ask this as the harder variant of adjacent duplicates removal. The (character, count) stack pair elegantly handles runs of any length and triggers removal when count reaches k.

Algorithmic pattern used

Stack of (char, count) pairs. For each character: if stack is non-empty and stack top character matches current, increment count. If count reaches k, pop the pair (group removed). Else push new pair (char, 1).

Example explanation

s="deeedbbcccbdaa", k=3. Process:

• d(1),e(1),e(2),e(3)→pop eee. d(1),b(1),b(2),c(1),c(2),c(3)→pop ccc. d(1),b(2+1=3)→pop ddd. Wait: stack after "eeee" removal: [d]. Continue: b,b,c,c,c→pop. b,d,a,a. Result: "aa".

Common mistakes candidates make

• Storing just characters without counts (can't efficiently detect k-length runs).
• Not handling the case where removal of k elements creates a new k-length run (stack handles this automatically).
• Off-by-one: trigger removal when count == k (not > k).
• Not joining the stack correctly at the end.

Interview preparation tip

String II extends String I by tracking run lengths. The (char, count) stack is the cleanest approach: each push either extends a run or starts a new one; when count reaches k, pop and remove. This automatically handles cascading removals. Practice: "decode string," "compress string with counts," "run-length decoding." The (char, count) stack is a versatile string compression tool.