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

这道题到底在问什么

输入

s="deeedbbcccbdaa", k=3

输出

"aa" （eee、bbb、ccc 等连环删除后只剩 aa）

输入

s="abcd", k=2

输出

"abcd" （没有任何 2 个相邻相同,原样返回）

先想最直接的笨办法

上方是输入串 s="abbbaaca",下方是空的计数栈。我们从最左边的字符开始,一个一个往栈里送。（动画第 4 步）

最优解：一步一步想明白

1. 3一句话套路:把「连续多少个」记在栈顶,凑满 k 就弹掉。弹掉后下一个字符自然去和新的栈顶比较,新相邻关系被自动处理。
2. 4上方是输入串 s="abbbaaca",下方是空的计数栈。我们从最左边的字符开始,一个一个往栈里送。
3. 5读到第 0 个字符 a,栈为空,它要作为新的一段压入栈。
4. 6a×1 压入栈顶。目前栈里拼起来是 "a",这就是「到此为止删不动的结果」。
5. 7读到第 1 个字符 b,和栈顶 a 不同,它要作为新的一段压入栈。
6. 8b×1 压入栈顶。目前栈里拼起来是 "ab",这就是「到此为止删不动的结果」。
7. 9读到第 2 个字符 b,它和栈顶的 b×1 是同一个字符,把栈顶的连续次数加一。
8. 10b 现在连续 2 个,还没到 k=3,先留在栈里继续等后面的 b。
9. 11读到第 3 个字符 b,它和栈顶的 b×2 是同一个字符,把栈顶的连续次数加一。
10. 12b 的连续次数达到 k=3,这一整段 b×3 被删除(弹出栈)。注意:删掉后,新的栈顶又要和后面的字符重新较量。
11. 13删除后,栈顶换成了下面那段 a×1。接下来的字符会去和这个新栈顶比较,被删段左右的字符就这样有机会接到一起。
12. 14读到第 4 个字符 a,它和栈顶的 a×1 是同一个字符,把栈顶的连续次数加一。
13. 15a 现在连续 2 个,还没到 k=3,先留在栈里继续等后面的 a。
14. 16读到第 5 个字符 a,它和栈顶的 a×2 是同一个字符,把栈顶的连续次数加一。
15. 17a 的连续次数达到 k=3,这一整段 a×3 被删除(弹出栈)。注意:删掉后,新的栈顶又要和后面的字符重新较量。
16. 18这一弹之后栈空了,后面的字符将作为全新的一段重新压入。
17. 19读到第 6 个字符 c,栈为空,它要作为新的一段压入栈。
18. 20c×1 压入栈顶。目前栈里拼起来是 "c",这就是「到此为止删不动的结果」。
19. 21读到第 7 个字符 a,和栈顶 c 不同,它要作为新的一段压入栈。
20. 22a×1 压入栈顶。目前栈里拼起来是 "ca",这就是「到此为止删不动的结果」。
21. 23所有字符扫完。把栈里剩下的每段「字符 ×次数」依次拼起来,就是最终答案 "ca"。中间 bbb 删掉后,左右的 a 接到一起也凑满 3 被删,这正是计数栈自动处理新相邻的威力。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        for ch in s:
            if stack and stack[-1][0] == ch:
                stack[-1][1] += 1
                if stack[-1][1] == k:
                    stack.pop()
            else:
                stack.append([ch, 1])
        return ''.join(ch * cnt for ch, cnt in stack)

#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char,int>> st;
        for (char c : s) {
            if (!st.empty() && st.back().first == c) {
                if (++st.back().second == k) st.pop_back();
            } else st.push_back({c, 1});
        }
        string ans;
        for (auto [c, cnt] : st) ans.append(cnt, c);
        return ans;
    }
};

import java.util.*;
class Solution {
    public String removeDuplicates(String s, int k) {
        Deque<int[]> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!st.isEmpty() && st.peek()[0] == c) {
                st.peek()[1]++;
                if (st.peek()[1] == k) st.pop();
            } else st.push(new int[]{c, 1});
        }
        StringBuilder ans = new StringBuilder();
        Iterator<int[]> it = st.descendingIterator();
        while (it.hasNext()) {
            int[] p = it.next();
            for (int i = 0; i < p[1]; i++) ans.append((char) p[0]);
        }
        return ans.toString();
    }
}

复杂度

面试官可能追问