Skip to main content

1047. Remove All Adjacent Duplicates In String

easy

Repeatedly delete adjacent equal letters until none remain. A clean one-pass stack problem that teaches the 'use the stack itself as your output buffer' trick.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them. We repeatedly make duplicate removals on s until we no longer can. Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Constraints

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

Examples

Example 1

Input
s = "abbaca"
Output
"ca"

Explanation: For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2

Input
s = "azxxzy"
Output
"ay"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

After you delete a pair, the characters on either side become adjacent. That cascade is exactly what a stack handles for free.

Hint 2

Scan left to right. If the new char equals the top of your stack, pop it; otherwise push.

Hint 3

Use a mutable char array/StringBuilder as the stack — pop = decrement length. Final answer is the buffer joined.

Hint 4

Each char is pushed and popped at most once: linear time.

Solution approach

Reveal approach

Single-pass stack. Walk s left to right with a stack (a mutable char buffer is perfect). For each character c: if the stack is non-empty and stack.top() == c, pop the top (the pair cancels). Otherwise push c. At the end, join the stack into a string and return it. The stack itself is the answer buffer — no extra collection needed. Each character is pushed once and popped at most once, so O(n) time and O(n) space worst case (e.g., 'abcdef' — nothing cancels).

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • stack
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Remove All Adjacent Duplicates In String and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →