The O(n) Club: Remove All Adjacent Duplicates in String II—Stack Attack Edition

The O(n) Club: Remove All Adjacent Duplicates in String II—Stack Attack Edition

⚡ TL;DR

Input: string + integer k. Goal: keep destroying any group of k identical neighbors in the string until it looks like it went through a laundry spin cycle. You could brute-force—if you hate your CPU. Just use a stack. Here’s how you probably thought of it at 2am—don’t actually do this:

// Please, don't try this at home...
while (string has k adjacent duplicates) {
    string = removeFirstKGroup(string, k);
}

🧠 How Devs Usually Mess This Up

Rookie mistake? Try removing all k-length duplicate groups in just one sweep. That misses the sneaky duplicates formed after removals, so you end up iterating endlessly or missing stuff. Others attempt recursion (hello, stack overflows!), or scan in n^2 time, linearly rebuilding the string on every delete. Yeah, let’s not.

🔍 What’s Actually Going On

Pretend your string is a tower of precarious crates. Knock out every stack of k identical crates when you see them. But when you do, crates above tumble down, possibly creating fresh removable stacks. Tracking that chaos by hand is miserable—so let a stack do the heavy lifting! For each incoming char, if it matches the last, increment a count; else, start a new streak. Count hits k? Out they go. Rinse, repeat, marvel at your clean(ish) string.

🛠️ PseudoCode

• Setup an empty Stack with entries like [char, count].

  // e.g. stack.push(['a', 1])

• For each character c in the input string:

  for each char c in s:

• If stack is empty or top char ≠ c:

  stack.push([c, 1]);

• If stack top is c, increment its count:

  stack.peek().count++;

• If count reaches k, pop that group:

💻 The Code

import java.util.*;
 public class Solution {
    static class Pair {
        char ch;
        int count;
        Pair(char ch, int count) { this.ch = ch; this.count = count; }
    }
    public String removeDuplicates(String s, int k) {
        Deque
<pair> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek().ch == c) {
                stack.peek().count++;
                if (stack.peek().count == k) {
                    stack.pop();
                }
            } else {
                stack.push(new Pair(c, 1));
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            Pair p = stack.removeLast();
            for (int i = 0; i < p.count; ++i) sb.append(p.ch);
        }
        return sb.toString();
    }
     public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.removeDuplicates("deeedbbcccbdaa", 3)); // "aa"
    }
}</pair>

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t assume you remove >k in one shot—remove only k; leftovers live on.
• Cascading removals: fresh groups arise after popping—stack naturally handles it (if you let it). Avoid manual re-check after each pop!
• Watch for “corner cases”: empty string, k bigger than input size, k == 1 (just… return empty string and embrace chaos).
• Time complexity: O(n). Space? O(n), if your entire string is a repeated letter and nothing dies till the last round.

🧠 Interviewer Brain-Tattoo

“In a world full of adjacent duplicates, be the stack: count, pop, and keep the rest guessing.”