#118

Remove All Adjacent Duplicates In String

easy

stringstack

You are given a string s of lowercase letters. A duplicate removal deletes two adjacent equal characters.

Repeatedly perform duplicate removals on s until no two adjacent characters are equal, then return the final string. The result is guaranteed to be unique.

Example

Input: s = "abbaca"

Output: "ca"

Remove "bb" to get "aaca", then "aa" to get "ca".

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters.

Intuition

The literal reading of the problem: scan for any two adjacent equal characters, delete them, and start over — because a deletion can create a new adjacent pair underneath. Repeat until a full scan finds nothing to remove.

function removeDuplicates(s) {
  let changed = true;
  while (changed) {
    changed = false;
    for (let i = 0; i + 1 < s.length; i++) {
      if (s[i] === s[i + 1]) {
        s = s.slice(0, i) + s.slice(i + 2); // cut the matching pair
        changed = true;
        break; // restart the scan from the top
      }
    }
  }
  return s;
}

Brute force — find and delete an adjacent pair, restart, until stable: O(n²).

Every deletion restarts an O(n) scan and rebuilds the string, so a long collapsing run is O(n²). Can we do better?

The key observation: a character only ever cancels against the character immediately before it in the result so far — the most recently kept one. “Compare against the most recent kept item, and remove it on a match” is a [stack](/study-guide/algos/topic/stacks). Push each character; but if it equals the current top, the two are an adjacent pair — pop the top instead, cancelling both. A pop can expose a new top, so the cascade is handled for free: the next character compares against whatever surfaced.

The characters left on the stack, in order, are the answer. The lane is the input being scanned; marked cells are characters that have cancelled away. Walking it through:

s = "azxxzy"

i↓

push 'a', push 'z'

Top differs each time, so both are kept. Stack: [a, z].

i↓

'x' != top 'z' → push

A new character, no match. Stack: [a, z, x].

i↓

'x' == top 'x' → pop

The second 'x' matches the top — they cancel. Stack: [a, z].

i↓

'z' == top 'z' → pop

Removing the x's exposed 'z' on top; the incoming 'z' cancels it too — the cascade. Stack: [a].

i↓

'y' != top 'a' → push

'y' doesn't match 'a', so it's kept. Stack: [a, y] → result "ay".

Optimization

Character stack

Build the result on a stack. For each character, if it equals the character currently on top of the stack, the two are an adjacent pair — pop the top instead of pushing, cancelling both. Otherwise push the character. Because a removal can expose a new adjacency underneath, the stack naturally handles the cascade: the next character is compared against whatever is now on top.

The characters left on the stack, in order, are the final string.

O(n) time, O(n) space.

function removeDuplicates(s) {
  const stack = [];
  for (const ch of s) {
    // If ch matches the top, they cancel — pop instead of push.
    if (stack.length > 0 && stack[stack.length - 1] === ch) {
      stack.pop();
    } else {
      stack.push(ch);
    }
  }
  return stack.join("");
}

Complexity analysis

Time complexity: O(n). Here's why:

Each character is pushed at most once and popped at most once.
The final join over the surviving characters is O(n).

So the whole process is O(n), where n is the string length — the brute force's restart-on-every-deletion is the O(n²) this replaces.

Space complexity: O(n). Here's why:

The stack holds the characters kept so far.
A string with no adjacent duplicates (e.g. "abcd") never pops, so every character is on the stack.

So the stack reaches n entries in the worst case — O(n) (also the size of the output string).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
s = "b"	"b"	Single character — nothing to cancel.
s = "cc"	""	One pair cancels to the empty string.
s = "xyx"	"xyx"	Equal characters but not adjacent — nothing cancels.
s = "deed"	""	Cascade: the inner 'ee' cancels, then the exposed 'dd' cancels too.
s = "abbaca"	"ca"	The example: 'bb' then 'aa' cancel, leaving 'ca'.
s = "pqrs"	"pqrs"	No adjacent duplicates — the string is unchanged.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor