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.

#1047

Easy

auto_awesome栈·状态

LeetCode 题解工作台

删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s ，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 s 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。示例：输入： "abbaca" 输出： "ca" 解释：例如，在 "abbaca" 中，…

字符串栈

题目描述

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= s.length <= 10⁵
s 仅由小写英文字母组成。

lightbulb

解题思路

方法一：栈

遍历字符串 s 中的每个字符 c，若栈为空或者栈顶值不等于字符 c，将 c 入栈，否则栈顶元素出栈。

最后返回栈中元素所组成的字符串。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串 s 的长度。

1

2

3

4

5

6

7

8

9

10

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1021 删除最外层的括号 #1081 不同字符的最小子序列 #1003 检查替换后的词是否有效