Remove Adjacent Duplicates II LeetCode 1209

LeetCode 1209 — Remove All Adjacent Duplicates in String II — gives you a string s and an integer k. Repeatedly remove groups of k adjacent identical characters from s until no more such groups exist. Return the final string after all removals.

For example, s = "deeedbbcccbdaa", k = 3. Remove "eee" → "dbbcccbdaa". Remove "ccc" → "dbbdaa" (note: this does not exist in that step). Actually remove "ccc" → "dbbdaa" → no triple adjacents. Wait — "dbbdaa" has no group of 3. The actual result after all removals is "aa".

The naive approach repeatedly scans the string for groups of k, which can take O(n^2/k) time. The stack approach processes the string in a single pass: maintain a stack of (character, count) pairs, incrementing the count when the same character appears consecutively and popping when the count reaches k.

Initialize an empty stack. For each character c in s: if the stack is non-empty and the top entry has the same character c, increment the top entry's count. Otherwise, push a new entry (c, 1) onto the stack.

After incrementing, check if the top count equals k. If so, pop the entry — this removes k consecutive identical characters. After the pop, if the new top has the same character as what we process next, the counts naturally merge in subsequent iterations.

This single-pass approach handles cascading removals automatically. When a group of k is removed, the characters below it on the stack become adjacent, and subsequent pushes may trigger further removals. No re-scanning is needed.

Consider s = "deeedbbcccbdaa", k = 3. Stack starts empty. d: push (d,1). e: push (e,1). e: top is (e,1), increment → (e,2). e: top is (e,2), increment → (e,3). Count = k = 3, pop! Stack: [(d,1)].

b: push (b,1). b: increment → (b,2). c: push (c,1). c: increment → (c,2). c: increment → (c,3). Count = 3, pop! Stack: [(d,1),(b,2)]. b: top is (b,2), increment → (b,3). Count = 3, pop! Stack: [(d,1)].

d: top is (d,1), increment → (d,2). a: push (a,1). a: increment → (a,2). Final stack: [(d,2),(a,2)]. Rebuild string: "ddaa". Wait — let me recheck. After popping the b's, d: top is (d,1), increment to (d,2). Then d again? No, next char after second b-pop is "d" from original. Stack: [(d,2)]. Then a: push (a,1). a: increment (a,2). Result: "ddaa".

After processing all characters, the stack contains (character, count) pairs representing the surviving characters. Iterate through the stack from bottom to top, appending each character repeated by its count.

In Python, use "".join(c * count for c, count in stack). In Java, use a StringBuilder and loop through the stack entries. The reconstruction is O(n) in the worst case (no characters removed).

An alternative implementation avoids the stack entirely by using a mutable string (list in Python, StringBuilder in Java) with a separate count array. The index into the string serves as the stack pointer. This is slightly more efficient due to cache locality but conceptually identical.

In Python: stack = []. For c in s: if stack and stack[-1][0] == c, stack[-1][1] += 1, else stack.append([c, 1]). If stack[-1][1] == k, stack.pop(). Return "".join(c * n for c, n in stack). Note: use lists [c, count] not tuples since we need to mutate the count.

In Java: use a Deque<int[]> where int[0] is the character and int[1] is the count. Or use two parallel arrays (char[] and int[]) with a pointer acting as stack top. The parallel array approach is faster due to no object allocation.

Edge cases: k = 1 removes every character (return ""). All characters the same and length is a multiple of k (return ""). String with no k-length groups (return original string). All three cases are handled naturally by the stack logic.

Time complexity is O(n) where n is the length of s. Each character is pushed onto the stack once and popped at most once. The count increment and k-check are O(1) per character. String reconstruction is O(n).

Space complexity is O(n) for the stack. In the worst case (no removals), the stack holds all n characters as (char, 1) entries. In the best case (everything removed), the stack ends empty but temporarily holds up to n entries.

This is optimal — we must read every character at least once, and the stack processes each character in amortized O(1) time. No re-scanning or multiple passes are needed.

Remove All Adjacent Duplicates in String (LeetCode 1047) is the k=2 version. It uses the same stack approach but pops when two consecutive characters match. Solving the k=2 version first builds intuition for the general k case.

Decode String (LeetCode 394) uses a stack to handle nested repetitions like "3[a2[c]]". While the encoding differs, both problems use stacks to manage string transformations that may cascade or nest.

Minimum Remove to Make Valid Parentheses (LeetCode 1249) uses a stack to track characters that need removal. The pattern of using a stack to process a string and remove invalid segments is shared across all these problems.