LeetCode 1647. 字符频次唯一的最小删除次数
题目描述
题意分析
删除尽可能少的字符，使剩余各字母的正频次互不相同。每个字母只能降低频次，删到零后就不再参与比较。原字符总数固定，因此最少删除等价于让最终保留的频次总和最大。
解法：频次集合去重
核心思路
[!blue]
用集合used记录已经选定的正频次。处理原频次为f的字母时，从f向下寻找最大的未占用频次；每减一就删除一个字符。若所有可用正频次都已占用，就降到零，把这个字母删光。这个选择可以按任意字母顺序进行。设已经处理的字母固定不动，当前最大可用频次为
g。某个最优方案给当前字母的频次a不可能大于g；若a < g，分两种情况：g没有被后续字母使用，就把当前频次提高到g；g已被后续字母使用，就交换它与当前字母的最终频次。交换始终合法：当前字母原频次足以保留
g，后续字母既然能保留g，也能保留更小的a；正频次仍不重复，保留总数不变。若a = 0，后续字母直接删光即可。因此总能让一个最优方案采用当前贪心选择，逐个固定后仍然最优。频次为零时不加入集合，因为零代表该字母已不存在，可以由多个字母同时取得。原本未出现的字母也直接跳过，不产生删除次数。
解题步骤
- 统计各字母次数。
- 逐个处理频次，正数且已被占用时递减并累计删除数。
- 剩余频次为正才登记到集合。
- 返回总删除数。
代码实现
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)$。统计扫描全部字符，每次递减都对应删除一个字符，总递减次数不超过 $n$；集合查询与插入期望为 $O(1)$。
- 空间复杂度：$O(1)$，频次数组和集合最多各保存 $26$ 项。
关键点总结
[!green]
- 集合保存调整后的频次，不是原频次。
- 零表示字母被删光，不要求唯一。
- 交换论证支持任意字母处理顺序。
易错点总结
[!yellow]
- 降到零仍继续减：会制造不存在的负频次。
- 调整后登记原频次：没有占住真正使用的新频次。
- 同频字母除一个外全部删光：减少到不同正数往往更省。
- 把未出现字母的零频次也要求互异：为不存在的字符额外计算删除。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1207. 独一无二的出现次数 | 简单 | 原题只判断频次是否互异，本题还通过删除字符使频次互异并最小化删除数。 |
| 945. 使数组唯一的最小增量 | 中等 | 原题通过增加值消除重复，本题通过降低频次消除重复，频次降到0表示整类删除。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！