#1047

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Remove All Adjacent Duplicates In String

Solve Remove All Adjacent Duplicates In String by simulating deletions with a stack that collapses matching neighbors immediately.

string stack

Problem Statement

In Remove All Adjacent Duplicates In String, you receive a lowercase string and may repeatedly delete any pair of equal neighboring characters. Each deletion can expose a new adjacent pair, so the process can keep cascading until no valid pair remains.

Your task is to return the final stable string after every possible adjacent duplicate has been removed. For example, processing "abbaca" removes "bb" first, which creates "aaca", then removes "aa", leaving "ca" as the unique final answer.

Examples

Example 1

Input: s = "abbaca"

Output: "ca"

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"

Example details omitted.

Constraints

1 <= s.length <= 105
s consists of lowercase English letters.

Solution Approach

Model the surviving characters as stack state

Treat the answer built so far as a stack. Read the string from left to right, and compare each new character with the current top. If they match, pop the top because this exact adjacent pair cancels out. If they differ, push the new character because it still survives for now.

Why the greedy pop is enough

This problem does not need backtracking across the full string because any new duplicate can only appear at the boundary created by the latest removal. The stack keeps that boundary available at all times. That is why chain reactions such as "azxxzy" collapsing to "ay" are handled correctly in one pass.

Build the final string from stack contents

After the scan finishes, the stack contains exactly the characters that were never canceled by an adjacent equal partner. Join those characters in order to form the result. This avoids repeated substring creation, which is the main performance trap in naive deletion simulations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

With the stack-based state management approach, each character is pushed at most once and popped at most once, so the total time is O(n). The extra space is O(n) in the worst case when no adjacent duplicates are removed and the entire string remains on the stack.

What Interviewers Usually Probe

They mention repeated removals causing new adjacent pairs, which is a strong signal to preserve evolving boundary state.
They ask for something better than simulating string deletions, which points away from costly rebuilds and toward a stack.
They emphasize that the final answer is unique, which supports a greedy left-to-right collapse strategy.

Common Pitfalls or Variants

Common pitfalls

Rebuilding the string after every deletion, which turns a simple stack problem into repeated O(n) work.
Using two pointers without stored history, which fails when a removal exposes a new match with an earlier surviving character.
Forgetting that chain reactions matter, so the code removes one pair but misses the next pair created immediately after the pop.

Follow-up variants

Remove adjacent duplicates when a character appears k times in a row, which extends the stack to store counts.
Return the length of the final collapsed string instead of the string itself, while using the same stack process.
Process a stream of characters and maintain the current deduplicated result online with stack state.

FAQ

What is the best approach for Remove All Adjacent Duplicates In String?

Use a stack to represent the current surviving characters. For each character, pop when it matches the top and push when it does not. That directly simulates adjacent removals and handles cascading deletions in one left-to-right pass.

Why does the stack pattern work for adjacent duplicate removal?

After a pair is removed, only one new comparison matters: the character now exposed at the end of the surviving prefix against the next incoming character. A stack stores exactly that boundary, so it captures every possible chain reaction without rescanning older parts of the string.

Can I solve this problem with repeated string replace operations?

You can, but it is usually inefficient because each removal may rebuild large parts of the string. On inputs up to 10^5 characters, repeated replacements or slicing can become much slower than the O(n) stack solution.

What happens on the example s = "abbaca"?

Push 'a', push 'b', then the next 'b' matches the top so pop. The next 'a' now matches the exposed top 'a', so pop again. Finally push 'c' and push the last 'a', producing "ca".

Is the final answer always unique in Remove All Adjacent Duplicates In String?

Yes. Even though you can imagine removals happening step by step, the problem guarantees the stable result is unique. That is why the greedy stack-based state management approach is safe for this exact problem.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stk = []
        for c in s:
            if stk and stk[-1] == c:
                stk.pop()
            else:
                stk.append(c)
        return ''.join(stk)

Continue Practicing

#1021 remove outermost parentheses #1081 smallest subsequence of distinct characters #1003 check if word is valid after substitutions