Remove All Adjacent Duplicates In String

1. Define the problem

Remove All Adjacent Duplicates In String

You are given a string s of lowercase letters. Repeatedly remove any two equal letters that sit next to each other , until no such pair is left. Return the string that remains. Removing a pair can create a brand new pair, so this has to keep going. In "abbaca", removing "bb" leaves "aaca", which now has "aa" next to each other, and removing that leaves "ca". A stack does all of this in one pass. Walk the letters left to right. If the next letter equals the letter on top of the stack, pop that top letter off — the pair cancels. Otherwise push the letter. Whatever is left on the stack, read bottom to top, is the answer.

Constraints

1 ≤ s.length ≤ 10⁵
s contains only lowercase English letters
The answer is unique no matter which pair you remove first

Example

Inputs = "abbaca"

Output"ca"

Explanation Remove "bb" to get "aaca", then remove "aa" to get "ca". No equal neighbours are left, so "ca" is the answer.

2. Know the words first

In plain terms

Adjacent: Sitting directly next to each other, with nothing in between.
Stack: A pile where you add and remove only at the top. Here the top always holds the last letter that survived.
One pass: Reading the input from start to end exactly once, instead of scanning it again after every removal.

3. Visualize the solution

The row is the stack of surviving letters, bottom-left to top-right

0—

1—

2—

3—

4—

5—

Statusinit

Start with an empty stack before reading "abbaca".

What happens in this step

s = "abbaca"
stack = []

No letters have survived yet, so every slot shows a dash.

Step 1 of 8

Steps to visualize

The row of cells is the stack. Cell 0 is the bottom, the last filled cell is the top.
Read the string one letter at a time.
If the letter matches the top of the stack, pop the top off — the pair cancels and both disappear.
If it does not match, push it on top.
At the end, join the filled cells left to right to get the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the stack of surviving letters, bottom-left to top-right

0—

1—

2—

3—

4—

5—

Statusinit

Start with an empty stack before reading "abbaca".

What happens in this step

s = "abbaca"
stack = []

No letters have survived yet, so every slot shows a dash.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function removeDuplicates(s) {
  const stack = [];

  for (const ch of s) {
    if (stack.length > 0 && stack[stack.length - 1] === ch) {
      stack.pop();
    } else {
      stack.push(ch);
    }
  }

  return stack.join('');
}

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

6. Test cases

Test cases

Input	Expected	Covers
`s = "abbaca"`	`"ca"`	example from the description, including a pair created by a removal
`s = "abc"`	`"abc"`	no two neighbours are equal, so nothing changes
`s = "aabb"`	`""`	the whole string disappears
`s = "a"`	`"a"`	smallest possible input
`s = "azxxzy"`	`"ay"`	one removal triggers the next, all the way down
`s = "aaa"`	`"a"`	three of the same letter leaves one behind

Remove All Adjacent Duplicates In String