Remove All Adjacent Duplicates in String II — Counter Stack Pattern

Problem Statement#

You are given a string s and an integer k. A k-duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k-duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed that the answer is unique.

Constraints:

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s consists of lowercase English letters.

Input:  s = "abcd", k = 2
Output: "abcd"

Input:  s = "deeedbbcccbdaa", k = 3
Output: "aa"

Input:  s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Why This Problem Matters#

LeetCode 1209 Remove All Adjacent Duplicates in String II is a perfect "stack with metadata" interview problem and shows up at Google, Amazon, Meta, and Bytedance. It is a direct extension of LeetCode 1047 (Remove All Adjacent Duplicates in String) where the trivial single-character pop generalizes to a count-based pop. The trap is a quadratic O(n times k) solution that tracks raw characters; the elegant linear solution uses a counter stack of (character, run length) pairs.

Recruiters ask this to confirm you can extend a basic stack pattern when the per-element state grows. It also tests string manipulation efficiency and your awareness of why naive splicing on a Python string or Java string costs O(n) per operation.

The Core Insight#

A naive approach scans the string repeatedly, removing one k-run at a time, costing O(n squared / k) in the worst case. We need to do everything in one pass.

The key observation: instead of pushing individual characters, push (character, count) pairs onto a stack. When the next character matches the top character, increment the top count. When the top count hits k, pop the entry — that simulates the removal. New adjacencies after removal are automatically exposed because the next character will be compared against whatever is now on top.

This is a generalization of the parentheses-matching pattern: the stack remembers exactly enough context (character and run length) to detect runs as they form, regardless of how many removals have already occurred.

Visual Dry Run#

s equals "deeedbbcccbdaa", k equals 3.

Final stack: [(a,2)]. Reconstruct: "aa". Matches expected output.

Notice how each character causes exactly one push and at most one increment plus one possible pop, keeping the algorithm linear.

Solution (Optimal)#

We use a list of pairs as the stack. Building the result string from the stack is O(n) at the end.

from typing import List
 
def removeDuplicates(s: str, k: int) -> str:
    stack: List[List] = []  # entries: [char, count]
    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)

function removeDuplicates(s, k) {
  const stack = []; // entries: [char, count]
  for (const ch of s) {
    if (stack.length && stack[stack.length - 1][0] === ch) {
      stack[stack.length - 1][1]++;
      if (stack[stack.length - 1][1] === k) stack.pop();
    } else {
      stack.push([ch, 1]);
    }
  }
  return stack.map(([ch, c]) => ch.repeat(c)).join('');
}

Complexity. Time O(n) — each character causes O(1) work. Space O(n) for the stack in the worst case (all distinct).

Common Mistakes#

• Storing only characters and re-scanning to count runs. This is O(n times k) in the worst case.
• Repeatedly calling string.replace or splice in a loop. Each operation is O(n), making the whole solution O(n squared / k) at best.
• Forgetting to handle the increment-to-k boundary. When count equals k, you must pop, otherwise subsequent characters will not see the correct top.
• Building the result with string concatenation in a loop. Use join with a generator or array map for O(n) reconstruction.
• Treating "adjacent" too literally and missing that removals can create new adjacencies. The stack handles this naturally.

Interview Tips#

• Open by describing the brute force and its quadratic cost. Then introduce the counter-stack twist as a one-line idea.
• Walk through the dry run on the whiteboard with k equal to 3 to highlight the cascading pops, especially the case where one removal exposes a new k-run.
• Mention this is a generalization of LeetCode 1047 — interviewers love seeing pattern recognition.
• Discuss the reconstruction step. Using an array map plus join is the canonical Python or JavaScript idiom and avoids quadratic concatenation.
• If asked, mention that the same idea generalizes to "remove runs of length at least k" with a slightly different pop condition.

Follow-up Questions#

1. What if k can change between operations? Re-run the algorithm with the new k; it stays O(n).
2. What if you must remove only the first occurrence per pass? Use a queue or repeated scans; the linear bound no longer holds.
3. What if characters carry weights and you must preserve total weight? Add a weight field to each stack entry.
4. How would you stream this with bounded memory? Stream characters and emit stable runs once they fall out of the bottom of the stack — but worst case still requires O(n) buffering.
5. What if k equals 1? Every character is removed; output is empty. Treat as an edge case or general case.

Key Takeaways#

• A counter stack of (character, count) pairs is the canonical way to handle "remove k adjacent duplicates."
• One pass, O(n) time, O(n) space — strictly better than any iterative replacement strategy.
• Stack pops naturally expose new adjacencies, eliminating the need for multi-pass scans.
• Build the result with a join over (character times count) to avoid quadratic concatenation.
• The pattern generalizes to any "merge consecutive runs" string operation.
• This is a direct extension of LeetCode 1047 — pattern recognition pays off.