The problem. Given a string s and an integer k, repeatedly remove k adjacent, equal letters until no such group is left, and return the final string. The answer is unique, whatever order the removals happen in.
s = "abcd", k = 2 -> "abcd" (nothing to remove)
s = "deeedbbcccbdaa", k = 3 -> "aa"
s = "pbbcggttciiippooaais", k = 2 -> "ps"Removing a group can make new neighbours meet — and they may complete another group. Rescanning the whole string after each removal works but is slow. A stack does it in one pass, because the only thing that can grow is the run just before the current letter: the top of the stack.
Store each run as a pair [letter, count]. A letter equal to the top run increases its count; when the count reaches k, pop the whole run — and the run underneath becomes the top, ready to be extended by the next letter. A different letter starts a new run.
function removeDuplicates(s, k) { let changed = true; while (changed) { // repeat until a pass removes nothing changed = false; for (let i = 0; i + k <= s.length; i++) { let j = i; while (j < s.length && s[j] === s[i] && j - i < k) j++; if (j - i === k) { // k equal letters start at i s = s.slice(0, i) + s.slice(i + k); // cut them out and start again changed = true; break; } } } return s;}Time O(n² / k), space O(n). There can be n / k removals, and each one rescans and rebuilds the string.
Each run sits on the stack with its length; reaching k pops it and lets the run below grow again.
function removeDuplicates(s, k) { const stack = []; // [character, how many in a row] for (const ch of s) { const top = stack[stack.length - 1]; if (top && top[0] === ch) { top[1]++; // one more of the same letter if (top[1] === k) stack.pop(); // k in a row: they vanish together } else { stack.push([ch, 1]); } } return stack.map(([ch, n]) => ch.repeat(n)).join("");}Time O(n), space O(n). Each letter is pushed or counted once and popped at most once.
Storing a count with each stack entry is the trick to remember: it turns "are the last k letters equal?" from a k-step check into a single comparison.
"abbbaaca", k = 3 → "ca")."aaaa" with k = 3 leaves "a": the count restarts after each removal.