LeetCode 1647. 字符频次唯一的最小删除次数

2021-09-01 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 1647. 字符频次唯一的最小删除次数

题意分析

给一个只含小写字母的字符串 s，每次操作可以删掉任意一个字符。要求删到「任意两个仍然出现过的字母，出现次数都不相同」为止，问最少删几个。

第一件要看清的事：删哪一个具体位置的字符完全无关紧要，只有「每个字母被删了几个」影响结果。所以输入的有效信息量只有 26 个计数，字符串的长度和排列方式都可以立刻丢掉。

第二件事：删除只能让计数变小，不能变大。这意味着每个字母的最终次数一定落在 $[0, cnt]$ 区间内，问题变成「给每个字母挑一个不超过它原始次数的目标值，要求这些目标值两两不同，使得原始次数与目标值之差的总和最小」。

第三件事是「仍然出现过」这个限定：次数降到 0 的字母被视为不存在，因此多个字母可以同时取 0，不算冲突。这是唯一一个允许重复的取值，也是很多实现出错的地方。

由于要最小化「原始总和减去目标总和」，而原始总和是常量，问题等价于最大化目标值之和。

数据规模上，字母只有 26 种，字符串长度上限 $10^5$。这说明统计频次是 $O(n)$，而后续的调整只需在 26 个数之间进行，几乎不占时间——出题人期待的是一遍统计加一遍贪心分配。

边界包括：所有字母次数本来就互不相同（答案 0）；只有一种字母（答案 0）；多个字母次数完全相同（会被迫压到 0）；以及被迫取 0 的字母不需要再和其他 0 冲突。

解法：频次集合去重

核心思路

暴力做法是枚举每个字母降到哪个值，$O(n^{26})$ 级别，完全不可行。即便改成搜索加剪枝，也远超必要。瓶颈在于把 26 个字母的取值当成了相互耦合的决策，而实际上它们之间只有「不能撞同一个正数」这一条约束。

观察点是：把每个正整数看成一个只能被一个字母占用的坑位，0 是一个可以无限容纳的公共坑位。每个字母只能往下走，所以它只能占用不超过自身原始次数的坑位。要最大化目标值之和，每个字母显然应该占「不超过它原始次数的、当前尚未被占用的最大坑位」。

贪心可用交换论证证明。处理原频次 f 时，设算法选择最大空位 x ≤ f。在一个兼容此前选择的最优分配中，当前字母若取更小的 y：若 x 没被使用，直接把 y 提到 x 会更优；若 x 被另一个尚未固定的字母使用，就交换两者的 x、y，后者既然能取 x，也一定能降到更小的 y，总保留量不变。因此总存在一个最优解与当前选择一致，逐个归纳即可证明贪心最优，处理顺序也不影响最少删除数。

不变量是：已处理字母占据互不相同的正数坑位或取 0，并且存在一个全局最优方案包含这些选择。向下找到第一个空位后，上述交换论证保证不变量继续成立；降到 0 时表示所有可保留的正数位置都已冲突，删光是唯一可行选择。

用一个集合记录「已被占用的正数坑位」，就能把「是否空位」的判断压成 $O(1)$。

解题步骤

先统计 26 个字母的出现次数。用长度 26 的数组而不是哈希表，因为字符集固定，数组的常数更小也更直观。

准备一个空集合，表示已被占用的正数坑位，另外准备答案累加器。集合初始必须为空——如果预先塞了任何值，第一个字母就会被迫多删。

逐个取出字母的次数 f，向下寻找空位：只要 f > 0 且 f 已被占用，就把 f 减 1 并把答案加 1。循环条件里的 f > 0 必须写在前面：它既保证不会降到负数，也体现了「0 是公共坑位，不需要继续找」。答案每次加 1，对应「为了腾出一个名次而删掉一个字符」。

循环结束后，只有 f > 0 时才把 f 写进集合。0 不写入是关键——写进去就等于宣称「0 这个坑位被占了」，后面本可以同样降到 0 的字母会被迫继续往下，而下面已经没有合法值了。

所有字母处理完毕，返回累加器。不需要额外排序，也不需要二次校验。

以 s = "aaabbbcc" 走一遍。统计得到 a → 3、b → 3、c → 2，其余字母为 0。

处理 a：f = 3，集合为空，3 未被占用，循环不进入，f > 0 所以把 3 写入集合，答案仍是 0。处理 b：f = 3，集合含 3，进入循环，f 变成 2、答案变成 1；此时 2 未被占用，退出循环，把 2 写入集合。处理 c：f = 2，集合含 2，进入循环，f 变成 1、答案变成 2；1 未被占用，退出，写入 1。其余字母 f = 0，循环条件 f > 0 直接为假，也不写入集合。

最终答案 2，对应把 b 删成 2 个、c 删成 1 个，三个字母的次数变成 3、2、1，互不相同。

再看 0 的用例 s = "aaabbbccc"（三个字母各 3 次）。a 占住 3；b 降到 2，答案 1；c 从 3 一路降：3 被占 → 2、答案 2；2 被占 → 1、答案 3；1 未被占 → 停在 1，写入集合。总答案 3，最终次数为 3、2、1。而若把用例换成 s = "aabbccdd" 这类四个字母各 2 次的情况，第一个占 2，第二个降到 1 花 1 次，第三个从 2 降到 0 花 2 次且不写入集合，第四个同样降到 0 花 2 次——两个字母同时取 0 互不冲突，总答案 5。

代码实现

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minDeletions(String s) {
        // 字符集固定为 26，用定长数组统计比哈希表更省常数。
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }

        Set<Integer> used = new HashSet<>();
        int answer = 0;
        for (int f : freq) {
            // 向下找第一个空坑位，每降一级就意味着删掉一个字符。
            while (f > 0 && used.contains(f)) {
                f--;
                answer++;
            }
            // 只登记正数坑位，0 是可以被多个字母共享的。
            if (f > 0) {
                used.add(f);
            }
        }
        return answer;
    }
}

func minDeletions(s string) int {
	// 字符集固定为 26，用定长切片统计比哈希表更省常数。
	freq := make([]int, 26)
	for i := 0; i < len(s); i++ {
		freq[int(s[i]-'a')]++
	}

	used := make(map[int]struct{})
	answer := 0
	for _, f := range freq {
		// 向下找第一个空坑位，每降一级就意味着删掉一个字符。
		for f > 0 {
			if _, ok := used[f]; !ok {
				break
			}
			f--
			answer++
		}
		// 只登记正数坑位，0 是可以被多个字母共享的。
		if f > 0 {
			used[f] = struct{}{}
		}
	}
	return answer
}

复杂度分析

时间复杂度：$O(n + \lvert\Sigma\rvert^2)$，其中 $n$ 是字符串长度、$\lvert\Sigma\rvert = 26$。统计频次扫描一遍字符串是 $O(n)$；后续外层循环 26 次，内层向下找空位时每前进一步都必然踩在一个已被占用的坑位上，而被占用的坑位总数不超过 26，所以单个字母的下降步数上界是 26。合起来后半部分是常数级，整体由 $O(n)$ 主导。

空间复杂度：$O(\lvert\Sigma\rvert)$，即 $O(1)$。频次数组固定 26 个元素，集合中最多存 26 个正数坑位，都与输入长度无关。

关键点总结

「最小化删除量」在这里等价于「最大化保留量」，把减法目标翻成加法目标之后，贪心的方向立刻变得清晰。遇到 min 型问题先看能不能转成 max 型，是个通用的破题手法。

把「取值不能重复」建模成「坑位只能被占一次」，再让每个元素取「不超过自身的最大空位」，是这类去重题的标准范式。同一范式可以直接迁移到「让数组元素互不相同的最少递减次数」。

0 是可共享的特殊坑位，必须在写入集合前显式排除。凡是题面里出现「仍然存在 / 非空 / 出现过」这类限定，都要检查是否存在这样一个不参与冲突的兜底取值。

贪心的正确性与遍历顺序无关，因为结论只依赖「最终占用的坑位集合」。能说清这一点，就不必先排序，也不会被面试官用「换个顺序会不会错」问倒。

字符集固定时，用定长数组代替哈希表，并把复杂度里的 $\lvert\Sigma\rvert$ 与 $n$ 分开写，比笼统写 $O(n)$ 更能体现对成本来源的把握。

面试视角：从「有效信息只有 26 个计数」开始讲，接着把问题重述为坑位分配，再给出贪心与它的交换论证，最后强调 0 的特殊性。面试官常追问「用排序后从大到小处理会不会更好」，答案是结果相同、复杂度也相同，排序只是让下降过程更容易口头论证；再追问「如果字符集是任意 Unicode」，回答是把频次收集到列表里再走同样流程，复杂度变成 $O(n + k^2)$，$k$ 为不同字符数。

易错点总结

错误写法：把 0 当成只能占一次的坑位，并继续向负数找空位。用例 s = "aabbccdd" 中两个字母都应允许删到 0；继续下降会制造不存在的负频次并多算删除。循环必须以 f > 0 为边界，0 也不能写入集合。

错误写法：找到空位后仍把原始频次写入集合。用例 s = "aaabbbcc" 中第二个 3 已降到 2，若仍登记 3，第三个字母会错误地继续占用 2，最终频次重复且答案少算 1。

错误写法：把答案算成「原始次数减去最终次数」时忘记累加，只在最后取一次差。用例 s = "aaabbbccc" → 只统计最后一个字母的下降量得到 2，实际答案是 3，漏掉了中间字母各自的删除量。

错误写法：认为次数相同的字母只需要留一个、其余全删。用例 s = "aaabbb" → 按这种想法要删掉 3 个，实际把其中一个降到 2 就够了，正确答案是 1。

错误写法：用集合记录「已出现过的原始频次」而不是「已被占用的最终频次」。用例 s = "aaabbbcc" → 集合初始化时把 3、3、2 全塞进去，处理 a 时发现 3 已在集合中就开始下降，凭空多删，答案变成 3，正确答案是 2。

错误写法：统计频次时把 26 个字母全部无条件加入待处理队列并要求它们互不相同。用例 s = "abc" → 23 个未出现的字母次数都是 0，若把 0 也当作必须唯一的取值，程序会试图把它们降到负数，答案变成正数，正确答案是 0。

错误写法：用 s.length() - used.size() 之类的公式反推答案。用例 s = "aaabbbcc" → 长度 8、集合最终大小 3，得到 5，正确答案是 2；删除量必须在下降过程中逐步累加，无法由规模直接推出。

错误写法：比较字母时用 s.charAt(i) - 'A' 或直接用字符值作下标。用例 s = "aab" → 下标算成 32 以上，Java 抛数组越界异常、Go 触发 panic。

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	只需比较两组频次是否完全相等，没有分配与调整环节
387. 字符串中的第一个唯一字符	简单	同样先统计频次，但第二趟要回到原串按位置找，考察两趟扫描的配合
451. 根据字符出现频率排序	中等	频次统计后按次数排序重建字符串，输出是构造结果而非计数
347. 前 K 个高频元素	中等	频次统计后取前 K，考点是堆或桶排序的选择，与冲突消解无关
621. 任务调度器	中等	频次决定答案，但约束是相同任务的最小间隔，需要按最高频次推导填空公式
767. 重构字符串	中等	同样由频次驱动，目标是构造相邻不同的排列，可行性由最大频次的上界决定
1200. 最小绝对差	简单	排序后相邻作差，是「先把无序信息整理成有序再一遍扫描」的最简形态
316. 去除重复字母	中等	也要按剩余频次做删或留的决策，但目标是字典序最小，需要单调栈而非坑位分配