1209. 删除字符串中的所有相邻重复项 II
题目描述
输入字符串 s 和整数 k。
一次操作从 s 中选出 k 个连续且相同的字母并删掉，删除处左右两侧随后拼在一起。
不断操作，直到再也找不到可删的部分。返回最终的字符串。题目保证结果唯一。
示例 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"
解释：逐对删去相邻重复字母后，只剩 ps。
数据范围
1 <= s.length <= 10^52 <= k <= 10^4s只含小写英文字母。
解题思路
和 1047 一样用栈，但栈里存“字符 + 连续次数”。读到的字符与栈顶字符相同就把次数加 1，次数达到 k 就整个弹出；否则压入 [c, 1]。弹出后栈顶变成更早的一段，它的计数还在，后面的同字符可以接着累加，连锁消除自动完成。
为什么正确
栈从底到顶是已扫描前缀完全消除后的结果（按连续段压缩），相邻两段字符不同，每段次数都小于 k。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
每次删除后从头重新扫描会变成 O(n^2/k)；栈里必须记录计数，否则无法在 O(1) 内判断栈顶是否已有 k 个。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = []
for c in s:
if stack and stack[-1][0] == c:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
else:
stack.append([c, 1])
return ''.join(c * cnt for c, cnt in stack)class Solution {
public String removeDuplicates(String s, int k) {
Deque<int[]> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peekLast()[0] == c) {
stack.peekLast()[1]++;
if (stack.peekLast()[1] == k) {
stack.pollLast();
}
} else {
stack.addLast(new int[]{c, 1});
}
}
StringBuilder sb = new StringBuilder();
for (int[] e : stack) sb.append(String.valueOf((char) e[0]).repeat(e[1]));
return sb.toString();
}
}class Solution {
public:
string removeDuplicates(string s, int k) {
vector<pair<char, int>> stack;
for (char c : s) {
if (!stack.empty() && stack.back().first == c) {
stack.back().second++;
if (stack.back().second == k) {
stack.pop_back();
}
} else {
stack.push_back({c, 1});
}
}
string res;
for (auto& [c, cnt] : stack) res.append(cnt, c);
return res;
}
};func removeDuplicates(s string, k int) string {
type pair struct {
c byte
cnt int
}
stack := []pair{}
for i := 0; i < len(s); i++ {
c := s[i]
if len(stack) > 0 && stack[len(stack)-1].c == c {
stack[len(stack)-1].cnt++
if stack[len(stack)-1].cnt == k {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, pair{c, 1})
}
}
res := []byte{}
for _, p := range stack {
for j := 0; j < p.cnt; j++ {
res = append(res, p.c)
}
}
return string(res)
}var removeDuplicates = function(s, k) {
const stack = [];
for (const c of s) {
if (stack.length && stack[stack.length - 1][0] === c) {
stack[stack.length - 1][1]++;
if (stack[stack.length - 1][1] === k) {
stack.pop();
}
} else {
stack.push([c, 1]);
}
}
return stack.map(([c, cnt]) => c.repeat(cnt)).join('');
};function removeDuplicates(s: string, k: number): string {
const stack: [string, number][] = [];
for (const c of s) {
if (stack.length && stack[stack.length - 1][0] === c) {
stack[stack.length - 1][1]++;
if (stack[stack.length - 1][1] === k) {
stack.pop();
}
} else {
stack.push([c, 1]);
}
}
return stack.map(([c, cnt]) => c.repeat(cnt)).join('');
}