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

2024-09-13 HGNULB 约 4 分钟

文章信息 8 个分类 2 个标签

分类

题目描述

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

题意分析

给一个小写字母串和整数 k，只要出现连续 k 个相同字符就把它们整体删掉，删完之后左右两侧会贴到一起，如果拼出了新的 k 连击还要继续删，一直删到没有为止，返回最终结果。

「删完之后左右贴合可能产生新的可删段」是这题的全部难点。它意味着删除不是一次性扫描能解决的局部操作，而是会向左传播的连锁反应。

一个容易被忽略但很重要的性质是：最终结果与删除顺序无关，无论先删哪一段，删到不能再删时得到的串都是同一个。所以不需要考虑「先删哪个更优」，只要保证不漏删即可。

约束信号是串长可以到 $4 \times 10^4$、k 最小为 1（此时任何字符都会被立即删光，结果是空串），这要求做到线性或接近线性，不能每删一次就重扫全串。

边界情形：k = 1 时结果一定是空串；整串同字符且长度不是 k 的整数倍时会剩下余数个字符；也可能一次都删不掉，原样返回。

解法：字符栈 + 连续计数

核心思路

删除一组相邻字符后，原本分开的两段可能重新相邻并触发下一次删除，因此需要保留当前未删除结果的末尾状态。用 StringBuilder 或字节切片充当字符栈，再用 count[top] 记录栈顶字符在当前位置结尾的连续次数。

新字符入栈后，若与前一个栈顶字符相同，计数加一；否则从 1 开始。计数达到 k 时，直接弹出末尾 k 个字符。弹出后旧前缀重新成为栈顶，它之前保存的计数仍然有效，可以自然处理连锁删除。

不变量：处理完输入前缀后，栈中恰好是该前缀执行完所有可触发删除后的结果，且每个栈位置的计数都表示以该位置结尾的连续同字符长度。

解题步骤

建立字符栈和与输入等长的计数数组。

依次把字符加入栈；根据前一栈顶字符计算当前位置的连续次数。

若次数等于 k，弹出栈尾的 k 个字符。

扫描结束后，栈中内容就是稳定结果。

例如 deeedbbcccbdaa、k = 3：先删除 eee 与 ccc，新相邻的 bbb 再被删除，最终得到 aa。连锁过程不需要回头重扫原串。

代码实现

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)$。每个字符入栈一次、被删除至多一次；Java 的尾部删除总量也不超过 $n$。

空间复杂度：$O(n)$。字符栈和计数数组最多保存全部输入。

关键点总结

连锁删除要求保存「删除后重新暴露的前缀状态」，栈正适合这一过程。

计数必须绑定栈位置，而不是绑定原字符串下标。

达到 k 时立即删除，保持栈内始终是当前前缀的稳定结果。

弹出后无须重新计算计数，旧栈顶的历史状态可以直接复用。

易错点总结

只统计原串连续段：删除后产生的新相邻关系会被漏掉。

只弹出一个字符：达到 k 时应删除整个长度为 k 的尾段。

删除后把旧栈顶计数清零：会破坏连锁合并所需的历史状态。

用全局字符频率判断删除：题目要求相邻，分散出现的相同字符不能合并。

每次删除后从头扫描：虽然可能正确，但最坏会退化到平方时间。

相似题目

题目	难度	考察点
316. 去除重复字母	中等	栈上做字典序贪心，弹出条件还要看后面是否还有
402. 移掉 K 位数字	中等	单调栈控制弹出次数，目标是最小数字串
1003. 检查替换后的词是否有效	中等	消除对象是固定子串 `abc`，只需判定不需构造
1047. 删除字符串中的所有相邻重复项	简单	`k` 固定为 2，栈里不必额外记连续长度