Remove All Adjacent Duplicates in String II: Stack-Based Character Counting

Remove All Adjacent Duplicates in String II is LeetCode 1209, rated Medium. You are given a string s and an integer k. Repeatedly remove groups of k adjacent identical characters until no more removals are possible, then return the final string. For example, with s = "deeedbbcccbdaa" and k = 3, the result is "aa".

If you have solved Remove All Adjacent Duplicates in String (the easy version where k = 2), this is the natural next step. The same stack intuition applies, but you need a small twist to handle arbitrary group sizes.

Why this problem matters

This problem teaches you how to extend a basic stack pattern to track additional state. The easy version only needed to compare two adjacent characters. Here, you need to count consecutive characters and only remove when the count reaches k. That counting extension is a pattern you will see in many stack problems where simple equality checks are not enough.

It also demonstrates cascading removals. Removing one group can bring previously separated characters together, forming a new group that also needs to be removed. A stack handles these cascading effects naturally because popping an entry exposes the entry beneath it, which may now merge with the next incoming character.

The key insight

The naive approach is to scan the string, find a group of k adjacent duplicates, remove it, and repeat. Each scan takes O(n) time, and in the worst case you might need O(n/k) rounds of scanning. That gives O(n^2/k) overall, which is too slow for large inputs.

The insight is to process the string in a single pass using a stack, but instead of pushing individual characters, push pairs of (character, count). When you encounter a character that matches the top of the stack, increment the count. When you encounter a different character, push a new pair with count 1.

The moment any entry's count reaches k, pop it immediately. That removal might expose the entry below it, and if the next character in the input matches that entry, the count keeps growing. This handles cascading removals without ever rescanning. Each character is pushed at most once and popped at most once, giving O(n) total time.

The solution

def removeDuplicates(s: str, k: int) -> str:
    stack = []
    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)

1. stack = []: Each entry will be a [character, count] pair tracking a run of identical characters.
2. for ch in s: Walk through the string one character at a time.
3. if stack and stack[-1][0] == ch: If the stack is non-empty and the top character matches the current one, we are extending an existing run.
4. stack[-1][1] += 1: Increment the count for the current run.
5. if stack[-1][1] == k: The moment the count hits k, we have found a group of k adjacent duplicates.
6. stack.pop(): Remove the entire group. This may expose the entry below, enabling cascading merges on the next iteration.
7. stack.append([ch, 1]): If the character does not match the top, start a new run with count 1.
8. ''.join(ch * count for ch, count in stack): Rebuild the result by repeating each character by its count.

Visual walkthrough

Notice the cascading effect in steps 8 and 9. After the three c's are removed, the b on top of the stack merges with the incoming b to form a group of 3, which is then removed. That exposes the d entries, and the same thing happens again. The stack handles all of this without backtracking through the string.

Complexity analysis

Time: O(n). Each character is processed exactly once. It either gets pushed as a new stack entry or merged into an existing one. Each stack entry is popped at most once. The total number of push and pop operations is bounded by 2n.

Space: O(n). In the worst case, every character is different and the stack holds n entries, each storing a character and a count. For example, s = "abcdef" with any k would produce a stack of size n.

Edge cases

• No groups of k exist: s = "aabbcc" with k = 3 has no group of 3 identical characters. Every character stays, and the output equals the input.
• Entire string vanishes: s = "aaabbbccc" with k = 3 removes all three groups. The stack ends up empty and the result is "".
• k = 1: Every character is immediately removed upon being pushed (count always reaches 1). The result is always "".
• k = 2: This reduces to the easier version of the problem (LeetCode 1047). The stack-with-counts approach still works, just with the threshold set to 2.
• Single character repeated: s = "aaaa" with k = 3 removes the first three a's, leaving "a".
• Long cascading removals: s = "deeedbbcccbdaa" with k = 3 triggers multiple cascading pops as shown in the walkthrough. The stack handles this in a single pass.

The building blocks

1. Stack with auxiliary count

The core pattern is extending a stack entry to carry extra information beyond just the value. Here, each entry stores (character, count). This same technique appears whenever you need to track "how many" or "how long" alongside the stack's primary data. For example, tracking frequencies in histogram problems or depths in nested structure problems.

stack = []
for ch in s:
    if stack and stack[-1][0] == ch:
        stack[-1][1] += 1
    else:
        stack.append([ch, 1])

2. Threshold-triggered pop

The second building block is popping an entry when a condition is met, not when a new element conflicts with the top. In the easy version, you pop when two adjacent characters match. Here, you pop when the count reaches a threshold. This generalizes to any situation where accumulation on the stack triggers a removal once some limit is hit.

if stack[-1][1] == k:
    stack.pop()

From understanding to recall

The solution is compact, but the details matter. Do you increment before checking the threshold, or after? Do you use tuples or lists for stack entries? How do you reconstruct the string from the stack at the end? Under interview pressure, small mix-ups in these details lead to bugs that eat up your debugging time.

Spaced repetition locks these details into long-term memory. Write the solution from scratch, wait a day, write it again. After a few cycles, the push-increment-check-pop sequence becomes automatic. You stop thinking about whether to check == k before or after the increment because your fingers already know the order.

Related posts

• Remove All Adjacent Duplicates in String - The easier version where k=2, using a simpler stack without counts
• Daily Temperatures - Another stack problem where you track indices and pop when a condition is met
• Valid Parentheses - The foundational stack matching pattern that underpins all push-and-pop string processing