让字符频率唯一的最少删除次数如何用贪心求解？

简化版

先统计每个字符频率，再让每个频率都唯一。对每个频率 f，如果它已经被占用，就不断减 1 并增加删除次数，直到 f=0 或遇到未占用频率。贪心点是每次尽量保留当前频率大一些，删除次数最少。

详细版

用 Set 记录已经使用过的频率。遍历字符频率时，若当前频率冲突，就持续 f--，每减一次代表删除一个字符。减到未使用频率后加入集合；如果减到 0，表示该字符全部删除，不需要把 0 加入集合。

因为只允许删除字符，频率只能下降不能上升，所以在冲突时把当前频率降到最近的可用频率是局部最优。时间复杂度近似 O(n + 字符种类 * 最大频率调整)，小写字母场景可视作 O(n)。

完整版教学

一、题目到底在约束什么

目标是让所有出现过的字符频率互不相同。比如 "aaabbbcc" 的频率是：

a:3
b:3
c:2

a 和 b 都是 3，冲突。我们可以删除一个 b，让频率变成 3,2,2，仍然冲突；更好的做法可能是把 b 降到 1，得到 3,1,2。

二、为什么只能向下调整频率

题目允许删除字符，不允许新增字符。所以频率只能从 f 变成 f-1, f-2, ... , 0，不能变大。

操作	频率变化
删除 1 个字符	`f -> f-1`
删除多个字符	`f -> 更小非负数`
新增字符	不允许

记忆钩子：频率唯一题，删除只能往下找坑位，不能往上补。

这个单向性让贪心变得自然：冲突时找离当前最近的空频率。

三、贪心策略为什么是“降到最近可用频率”

如果频率 f 已经被用过，当前字符必须降低到某个未使用频率。降低得越少，删除次数越少，并且保留更多字符不会让后续更难，因为使用的是最靠近 f 的空位。

已用频率：{3,2}
当前 f=3
可选降到：1 或 0
降到 1 删除 2 个，比降到 0 删除 3 个更好

这就是局部最优：在所有合法下降结果里，选择最大可用频率。

四、用 Set 维护已用频率

遍历每个字符的频率：

while f > 0 && used contains f:
    f--
    deletions++
if f > 0:
    used.add(f)

0 不加入集合，因为多个字符都删光是允许的；它们已经不再出现，不参与“出现字符频率唯一”的约束。

频率 [3,3,2]
第一个 3：used={3}
第二个 3：降到 1，used={3,1}
2：used={3,1,2}

总删除 2。

五、代码模板

int minDeletions(String s) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    Set<Integer> used = new HashSet<>();
    int ans = 0;
    for (int f : cnt) {
        while (f > 0 && used.contains(f)) {
            f--;
            ans++;
        }
        if (f > 0) used.add(f);
    }
    return ans;
}

如果字符集不是小写字母，可以用 Map<Character, Integer> 统计，后面的贪心逻辑不变。

六、为什么遍历顺序通常不影响结果

因为每个频率冲突时都会下降到当前可用的最高位置。也可以先把频率降序排序，再处理，这样直觉上更清楚：大频率优先占大坑，小频率往下挪。

写法	特点
Set 直接处理	代码短，小写字母常用
频率排序后处理	证明更直观

对于小写字母最多 26 种，任意写法性能都足够。

七、常见误区与追问

误区：把冲突频率统一减 1 就结束。 减 1 后仍可能和其他频率冲突，要循环检查。
误区：把频率 0 加入 used。 多个字符被删光是允许的，0 不应参与唯一性。
误区：试图把小频率增加。 题目只能删除，不能新增字符。
追问：为什么降到最近可用频率最优？ 删除次数最少，且不会占用比它更高的可用位置。
追问：字符集很大怎么办？ 用 HashMap 统计频率，再用 HashSet 处理已用频率。
追问：复杂度如何？ 统计是 O(n)，调整次数不超过删除总次数，整体可接受。

八、加强记忆

让频率唯一的关键是“频率只能往下掉”。每个字符拿着自己的频率去找坑，坑被占了就删一个字符继续往下找；找到空坑就占住，掉到 0 就代表删没了。Set 记录已用频率，while 负责处理连续冲突，别只减一次就停。

简化版

详细版