What is the core approach to solving the Remove All Adjacent Duplicates in String II problem?

The key approach involves using a stack to track characters and their counts. When the count reaches k, you remove the characters from the stack.

How do stacks help in solving the Remove All Adjacent Duplicates in String II problem?

Stacks manage character sequences efficiently by pushing characters and popping them when k adjacent duplicates are found, which simplifies the removal process.

What are the time and space complexities for the Remove All Adjacent Duplicates in String II problem?

Typically, the time complexity is O(n), and space complexity is O(n) due to the stack-based solution.

How do edge cases affect the solution for Remove All Adjacent Duplicates in String II?

Edge cases like no duplicates or large values of k can affect performance. Efficient stack management ensures optimal handling in these cases.

What can be done to optimize the solution for the Remove All Adjacent Duplicates in String II problem?

Optimizing the solution involves ensuring that the stack only holds necessary characters and avoiding repeated string concatenations during the process.

#1209

Medium

auto_awesome栈·状态

LeetCode 题解工作台

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

给你一个字符串 s ，「 k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。在执行完所有删除操作后，返回最终得到的字符串。本题答案保证唯一。示例 1：输入： s …

字符串栈

题目描述

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小写英文字母。

lightbulb

解题思路

方法一：栈

我们可以遍历字符串 $s$ ，维护一个栈，栈中存储的是字符和该字符出现的次数。当遍历到字符 $c$ 时，如果栈顶元素的字符和 $c$ 相同，则将栈顶元素的次数加一，否则将字符 $c$ 和次数 $1$ 入栈。当栈顶元素的次数等于 $k$ 时，将栈顶元素出栈。

遍历完字符串 $s$ 后，栈中存储的就是最终结果。我们可以将栈中的元素依次弹出，拼接成字符串即可。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = []
        for c in s:
            if stk and stk[-1][0] == c:
                stk[-1][1] = (stk[-1][1] + 1) % k
                if stk[-1][1] == 0:
                    stk.pop()
            else:
                stk.append([c, 1])
        ans = [c * v for c, v in stk]
        return "".join(ans)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Ability to manage stack operations effectively under constraints.
question_mark
Handling edge cases such as no adjacent duplicates or very large inputs.
question_mark
Efficient handling of string processing using stack-based state management.

warning

常见陷阱

外企场景

error
Failing to correctly manage the stack during consecutive removals, leading to incorrect outputs.
error
Not correctly handling cases where no characters can be removed, resulting in inefficient operations.
error
Overcomplicating the problem by using unnecessary additional data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the value of k to test scalability.
arrow_right_alt
Modify the input to include no adjacent duplicates and check if the solution performs optimally.
arrow_right_alt
Test with large inputs to evaluate the time and space complexity of the solution.

help

常见问题

外企场景

继续练习

#1190 反转每对括号间的子串 #1249 移除无效的括号 #1111 有效括号的嵌套深度