What is the time complexity of this approach?

The time complexity is O(n), where n is the length of the string, as each character is processed once.

How does the stack help in solving the problem?

The stack allows for efficient management of the string state, by pushing characters and removing them when adjacent matching ones are found.

What happens if the string has no adjacent matching characters?

If no adjacent matching characters exist, the stack will simply contain the original string as is, with no changes made.

What are the edge cases for this problem?

Edge cases include strings that are already reduced, strings with alternating characters, and strings that result in an empty string after removals.

How can this solution be optimized for large inputs?

The solution is already optimized with O(n) time and space complexity, ensuring efficient processing even for strings with lengths up to 10^5.

#3561

Medium

auto_awesome栈·状态

LeetCode 题解工作台

移除相邻字符

给你一个由小写英文字母组成的字符串 s 。你必须在字符串 s 中至少存在两个连续字符时，反复执行以下操作：移除字符串中最左边的一对按照字母表连续的相邻字符（无论是按顺序还是逆序，例如 'a' 和 'b' ，或 'b' 和 'a' ）。将剩余字符向左移动以填补空隙。当无法再执行…

字符串栈模拟

题目描述

给你一个由小写英文字母组成的字符串 s。

你必须在字符串 s 中至少存在两个连续字符时，反复执行以下操作：

移除字符串中 最左边 的一对按照字母表连续的相邻字符（无论是按顺序还是逆序，例如 'a' 和 'b'，或 'b' 和 'a'）。
将剩余字符向左移动以填补空隙。

当无法再执行任何操作时，返回最终的字符串。

注意：字母表是循环的，因此 'a' 和 'z' 也视为连续。

示例 1：

输入: s = "abc"

输出: "c"

解释:

从字符串中移除 "ab"，剩下 "c"。
无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 "c"。

示例 2：

输入: s = "adcb"

输出: ""

解释:

从字符串中移除 "dc"，剩下 "ab"。
从字符串中移除 "ab"，剩下 ""。
无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 ""。

示例 3：

输入: s = "zadb"

输出: "db"

解释:

从字符串中移除 "za"，剩下 "db"。
无法进行进一步操作。因此，所有可能移除操作后的最终字符串为 "db"。

提示:

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

lightbulb

解题思路

方法一：栈

我们可以使用栈来模拟移除相邻字符的过程。遍历字符串中的每个字符，如果栈顶字符与当前字符是连续的（即它们的 ASCII 值差为 1 或 25），则将栈顶字符弹出；否则，将当前字符压入栈中。最后，栈中的字符就是无法再移除的结果，我们将栈中的字符连接成字符串并返回。

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

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Efficient handling of large strings with minimal overhead.
question_mark
Understanding of stack-based algorithms.
question_mark
Ability to identify and address edge cases in string manipulation.

warning

常见陷阱

外企场景

error
Forgetting to handle cases where no characters can be removed.
error
Misunderstanding the stack's behavior when removing characters.
error
Failing to optimize for performance with large input sizes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider implementing this approach using a different data structure, such as a queue, to explore alternative solutions.
arrow_right_alt
Implement a variant that handles strings with special characters or case sensitivity.
arrow_right_alt
Modify the problem to allow multiple removals of different types of adjacent characters.

help

常见问题

外企场景

继续练习

#3412 计算字符串的镜像分数 #3174 清除数字 #2696 删除子串后的字符串最小长度