StackMediumO(n) time · O(n) space

Remove All Adjacent Duplicates in String II

Ramayana — The K-Fold Echo — Eliminating Any Word Repeated K Times in Succession

यदा एकः शब्दः क-वारं क्रमशः उच्यते। तत् सर्वं विलोपयेत् — शुद्धं वचनं पुनः प्रवर्तेत॥

*When one word is spoken k times in succession — erase all of them. Let the pure speech resume.*

The Story

Like st-1 but generalized: remove k adjacent duplicates (not just pairs).

For `s = "deeedbbcccbdaa"`, k=3: - `ddd` → remove → `"debbcccbdaa"`... actually let's be precise: - Remove `eee` (3 e's) → `"dbbcccbdaa"` - Remove `ccc` → `"dbbdaa"` - Remove `bb` — only 2, not 3; stays - Remove `aa` — only 2; stays - Final: `"dbbdaa"` ? Let's retrace:

`s = "deeedbbcccbdaa"`, k=3: Stack of `(char, count)` pairs: - 'd': [(d,1)] - 'e': [(d,1),(e,1)] - 'e': [(d,1),(e,2)] - 'e': [(d,1),(e,3)] → count==k → POP! [(d,1)] - 'd': top is (d,1), same char → [(d,2)] - 'b': [(d,2),(b,1)] - 'b': [(d,2),(b,2)] - 'c': [(d,2),(b,2),(c,1)] - 'c': [(d,2),(b,2),(c,2)] - 'c': [(d,2),(b,2),(c,3)] → POP! [(d,2),(b,2)] - 'b': top is (b,2) → [(d,2),(b,3)] → POP! [(d,2)] - 'd': top is (d,2) → [(d,3)] → POP! [] - 'a': [(a,1)] - 'a': [(a,2)]

Stack=[(a,2)] → result: `"aa"`

"The (char, count) pair tracks current run length," Valmiki noted. "When count reaches k, the entire run is eliminated — and this may cascade! After removing `ccc`, the two `b`s on each side are now adjacent (count=3 → eliminate), which makes two `d`s adjacent (also hitting k=3... wait, only 2+1=3!). Cascading eliminations happen automatically because the stack re-checks after each pop."

This cascade is handled automatically: after popping (c,3), the next 'b' extends (b,2) to (b,3) → pop → etc.

The Repeated Scanner

Repeatedly scan string for k consecutive same chars, remove them. Repeat until no more k-groups. O(n²/k).

java

public String removeDuplicatesBruteForce(String s, int k) {
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i <= s.length()-k; i++) {
            String sub = s.substring(i, i+k);
            if (sub.chars().distinct().count() == 1) {
                s = s.substring(0,i) + s.substring(i+k);
                changed = true; break;
            }
        }
    }
    return s;
}

The (char,count) Stack Wisdom

Stack of (char, count) pairs. For each character: if top has same char, increment count; else push (c,1). After incrementing: if count==k, pop. Cascading is automatic. Rebuild string from remaining stack.

java

public String removeDuplicates(String s, int k) {
    Deque<int[]> stack = new ArrayDeque<>();  // [char as int, count]
    for (char c : s.toCharArray()) {
        if (!stack.isEmpty() && stack.peek()[0] == c) {
            stack.peek()[1]++;  // Extend current run
            if (stack.peek()[1] == k) stack.pop();  // Remove complete k-run
        } else {
            stack.push(new int[]{c, 1});  // New run
        }
    }
    // Rebuild string
    StringBuilder sb = new StringBuilder();
    // Stack is LIFO — collect and reverse
    Deque<int[]> temp = new ArrayDeque<>();
    while (!stack.isEmpty()) temp.push(stack.pop());
    while (!temp.isEmpty()) {
        int[] top = temp.pop();
        for (int i = 0; i < top[1]; i++) sb.append((char) top[0]);
    }
    return sb.toString();
}

Step-by-Step Walkthrough

s="aabbcc", k=2
(a,1)→(a,2)→POP []
(b,1)→(b,2)→POP []
(c,1)→(c,2)→POP []
Stack empty → return "" ✅

Deep Insight

**Why cascading works automatically?** When (b,2) becomes (b,3) [count==k] → pop. Now the character after this group was already on the stack before the b-run began. If it matches what was below b on the stack, those are adjacent and will merge on the NEXT character's push — or the current character naturally extends the count.

**Wait — there's a subtlety:** Cascading happens because after popping (b,3), the next character extends the stack's new top if it matches. E.g.: `"aabbbaa"`, k=3 → push (a,2), (b,3)→POP, next 'a' finds (a,2)→(a,3)→POP.

**st-1 is st-7 with k=2.** This is the full generalization.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²/k)	O(n)	Repeated full scans
Optimal	O(n)	O(n)	Each char processed once; stack has at most n/k entries

Pattern Recognition

✅ Remove k adjacent same characters (cascading)
✅ Stack of (char, count) pairs
✅ Extend run if top matches; pop when count==k
✅ Generalization of st-1 (k=2 is the pair case)

**LeetCode Trigger Phrases:**
→ "remove all adjacent duplicates in string II"
→ "remove k consecutive same characters"
→ Cascading removal of groups

Bhagavad Gita 18.66

यदि तेषाम् अप्रतिकारो जायते तदा मयि शरणम् आगच्छ। अहं त्वां सर्वपापेभ्यो मोक्षयिष्यामि मा शुचः॥

Abandon all varieties of dharma and simply surrender unto Me. I shall deliver you from all sinful reactions; do not fear.

Connection: When a run of k identical characters accumulates, they are released — not one by one, but all at once. Like divine grace that erases accumulated karma completely when one fully surrenders, the pop happens exactly at k, cleansing the entire group simultaneously. The cascading nature mirrors karma's chain reaction: one release can trigger another, purifying the string layer by layer until only the genuine, non-repetitive core remains.