Remove Adjacent Duplicates | Stack | Stack

Overview

Remove adjacent duplicates: repeatedly remove two adjacent duplicate characters until no more can be removed (e.g. "abbaca" → "ca"). Use a stack: for each character, if it equals the top of the stack, pop; otherwise push. The stack is the current string without adjacent duplicates; join at the end.

When to Use

Remove pairs of adjacent same chars — stack: match with top, pop; else push.
Remove k adjacent same chars — stack of (char, count); when count reaches k, pop.
Candy crush / match-3 style — same "collapse when run length ≥ k" idea.

How It Works

One pass. Stack = "result so far" with no adjacent duplicates. New char: if same as top, pop (cancel pair); else push. Final string = stack joined.

Example 1: Standard (Remove 2 Adjacent)

function removeDuplicates(s: string): string {
  const stack: string[] = [];
  for (const c of s) {
    if (stack.length > 0 && stack[stack.length - 1] === c) stack.pop();
    else stack.push(c);
  }
  return stack.join('');
}

Time: O(n). Space: O(n).

Example 2: Remove K Adjacent Duplicates

Remove k or more adjacent same characters. Store (char, count). Push: if same as top, increment count; if count === k, pop; else push (c, 1). New char different from top: push (c, 1).

function removeDuplicatesK(s: string, k: number): string {
  const stack: [string, number][] = [];
  for (const c of s) {
    if (stack.length > 0 && stack[stack.length - 1][0] === c) {
      stack[stack.length - 1][1]++;
      if (stack[stack.length - 1][1] === k) stack.pop();
    } else stack.push([c, 1]);
  }
  return stack.map(([ch, cnt]) => ch.repeat(cnt)).join('');
}

Example 3: Step-by-Step Trace

s = "abbaca". a: push → [a]. b: push → [a,b]. b: same as top, pop → [a]. a: push → [a,a]. a: same as top, pop → [a]. c: push → [a,c]. Result "ac".

Example 4: Edge Cases

Empty string: stack stays empty → "".
All duplicates: "aaaa" → push, pop, push, pop → "".
No duplicates: "abc" → [a,b,c] → "abc".
Alternating: "abab" → no adjacent same → "abab".

Example 5: In-Place with Two Pointers (Optional)

Use a slow index as "stack top": result[0..slow] is the current string. For each char, if slow ≥ 0 and result[slow] === c, slow--; else result[++slow] = c. Return result.slice(0, slow + 1). Same logic, O(1) extra space if we can overwrite input.

Summary

Remove 2 adjacent: stack; if top === c pop else push; join stack.
Remove k adjacent: stack of (char, count); increment or push; pop when count === k. See Stack Basics.

Remove All Adjacent Duplicates