LeetCode 1209. 删除字符串中的所有相邻重复项 II
题目描述
题意分析
删除连续
k个相同字符，删除后重新相邻的字符仍可继续消除，返回稳定后的字符串。
解法：字符栈 + 连续计数
核心思路
[!blue]
从左到右读入字符，用
stack保存已处理前缀完成所有删除后的结果。这个结果中已经没有连续k个相同字符；追加一个新字符时，只有栈尾的连续段可能发生变化，因此不必重新扫描整个字符串。
count[top]表示以栈位置top结尾的连续同字符数量。把当前字符入栈后，若它与前一个栈位置的字符相同，就令count[top] = count[top-1]+1；否则从 1 开始。计数跟随当前栈位置，而不是当前字符在原串中的下标，因为删除会缩短栈。当
count[top] == k时，删除末尾这k个字符。剩余字符是旧栈的一个前缀，其字符和对应计数都没有改变，露出的旧栈顶计数仍然有效；后续字符可以接着与它合并。被删除位置留下的计数不用清零，之后复用该位置时会重新赋值。每轮只追加一个字符，最多让末尾一段刚好达到
k；删掉它后，剩余前缀本来就已无法继续删除，所以一次if足够。逐个处理后续字符便能完成连锁消除，读完时栈中留下的就是最终结果。
解题步骤
- 创建空字符栈，以及按栈位置存储的计数数组。
- 读入当前字符并入栈，令
top为新的栈顶下标。- 若前一个栈字符与当前字符相同，沿用它的计数加一；否则将当前计数设为 1。
- 计数达到
k时，删除整个末尾长度为k的片段，保留更早位置的计数。- 所有字符处理完后，将剩余栈内容作为字符串返回。
代码实现
class Solution {
public String removeDuplicates(String s, int k) {
StringBuilder stack = new StringBuilder();
int[] count = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
char current = s.charAt(i);
stack.append(current);
int top = stack.length() - 1;
// 计数绑定当前栈位置，复用未删除前缀的历史状态
count[top] = top > 0 && stack.charAt(top - 1) == current ? count[top - 1] + 1 : 1;
// 整组弹出后保留旧栈顶计数，等待后续连锁合并
if (count[top] == k) {
stack.delete(stack.length() - k, stack.length());
}
}
return stack.toString();
}
}
func removeDuplicates(s string, k int) string {
stack := make([]byte, 0, len(s))
count := make([]int, len(s))
for i := 0; i < len(s); i++ {
current := s[i]
stack = append(stack, current)
top := len(stack) - 1
// 计数绑定当前栈位置，复用未删除前缀的历史状态
if top > 0 && stack[top-1] == current {
count[top] = count[top-1] + 1
} else {
count[top] = 1
}
// 整组弹出后保留旧栈顶计数，等待后续连锁合并
if count[top] == k {
stack = stack[:len(stack)-k]
}
}
return string(stack)
}
复杂度分析
- 时间复杂度：$O(n)$，
n为字符串长度，每个字符入栈一次、至多删除一次，且删除始终发生在栈尾。- 空间复杂度：$O(n)$，字符栈与计数数组。
关键点总结
[!green]
- 计数绑定栈位置，不是原串位置。
- 成功删除后较早计数仍然有效。
易错点总结
[!yellow]
- 只按原串连续段删除，漏掉拼接后的连锁。
- 达到阈值只弹一个字符，没有移除完整组。
- 重置暴露的旧计数，丢掉跨删除区间的合并信息。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 从删除相邻两个扩展到k个，栈内需记录当前连续次数，删除后可能继续与前段合并。 |
| 443. 压缩字符串 | 中等 | 游程计数是基础，本题达到k后删除会产生新的相邻关系，不能只静态编码一次。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！