字符频次唯一的最小删除次数 图解题解
这道题到底在问什么
- 输入
- s = "aab"
- 输出
- 0 (频次 2 和 1 本就不同)
- 输入
- s = "aaabbbcc"
- 输出
- 2 (把频次调成 3、2、1)
最优解：一步一步想明白
- 3核心就一句:频次撞车就往下退一格,退到空位为止;退几格就删几个。下面每一帧都在套这套规则。
- 4先统计:a、b、c 都出现 5 次,d、e 都出现 2 次。下面每个柱子上的数字就是该字符的频次,我们要把这些数字调成两两不同。
- 5轮到字符 a(紫色),它现在出现 5 次。看看频次 5 是否已被前面的字符占用。
- 6频次 5 还没人占,a 就定在 5(变绿,加进右侧「已占用」)。a 处理完毕,继续下一个字符。
- 7轮到字符 b(紫色),它现在出现 5 次。看看频次 5 是否已被前面的字符占用。
- 8频次 5 已经在「已占用」里(右侧高亮),b 不能也用 5。删掉一个 b,频次降到 4。
- 9删除计数变成 1。b 现在频次 4,继续看 4 是否被占用。
- 10频次 4 还没人占,b 就定在 4(变绿,加进右侧「已占用」)。b 处理完毕,继续下一个字符。
- 11轮到字符 c(紫色),它现在出现 5 次。看看频次 5 是否已被前面的字符占用。
- 12频次 5 已经在「已占用」里(右侧高亮),c 不能也用 5。删掉一个 c,频次降到 4。
- 13删除计数变成 2。c 现在频次 4,继续看 4 是否被占用。
- 14频次 4 已经在「已占用」里(右侧高亮),c 不能也用 4。删掉一个 c,频次降到 3。
- 15删除计数变成 3。c 现在频次 3,继续看 3 是否被占用。
- 16频次 3 还没人占,c 就定在 3(变绿,加进右侧「已占用」)。c 处理完毕,继续下一个字符。
- 17轮到字符 d(紫色),它现在出现 2 次。看看频次 2 是否已被前面的字符占用。
- 18频次 2 还没人占,d 就定在 2(变绿,加进右侧「已占用」)。d 处理完毕,继续下一个字符。
- 19轮到字符 e(紫色),它现在出现 2 次。看看频次 2 是否已被前面的字符占用。
- 20频次 2 已经在「已占用」里(右侧高亮),e 不能也用 2。删掉一个 e,频次降到 1。
- 21删除计数变成 4。e 现在频次 1,继续看 1 是否被占用。
- 22频次 1 还没人占,e 就定在 1(变绿,加进右侧「已占用」)。e 处理完毕,继续下一个字符。
- 23处理完所有字符,各字符频次变成 a:5、b:4、c:3、d:2、e:1,彼此都不相同。一路删了 4 个字符,这就是答案。
⚠️ 容易写错的地方
✗ 错：把频次减到 0 后还往 used 里塞 0
✓ 对：只有频次大于 0 才加入 used
频次 0 表示该字符被删光,本就不算一种出现,不应占用频次
✗ 错：while 里忘了同步累加删除次数
✓ 对：每减 1 都要 ans += 1
删除次数就等于所有频次被往下压的总格数
✗ 错：想着「让大的让给小的」反复横跳
✓ 对：每个频次各自一路向下找空位即可
贪心地各自向下避让就是最优,不需要全局回头调整
完整代码（Python / C++ / Java）
Python
from collections import Counter
class Solution:
def minDeletions(self, s: str) -> int:
used = set()
ans = 0
for f in Counter(s).values():
while f > 0 and f in used:
f -= 1
ans += 1
if f:
used.add(f)
return ansC++
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
int minDeletions(string s) {
vector<int> count(26);
for (char c : s) count[c-'a']++;
unordered_set<int> used;
int ans = 0;
for (int f : count) {
while (f > 0 && used.count(f)) { f--; ans++; }
if (f) used.insert(f);
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int minDeletions(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
Set<Integer> used = new HashSet<>();
int ans = 0;
for (int f : count) {
while (f > 0 && used.contains(f)) { f--; ans++; }
if (f > 0) used.add(f);
}
return ans;
}
}复杂度
时间
O(n + A)
n 是串长用于计数;A 是字符种类数(≤26),每种字符向下避让的总格数不超过总频次,集合查改是常数。小写字母约束下整体就是 O(n)
空间
O(A)
频次表与 used 集合都只和字符种类数有关,最多 26
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 字符频次唯一的最小删除次数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
处理频次的顺序会影响最终答案吗?+
不会影响最终删除次数。无论先处理哪种字符,撞车时各自向下找最近空位,总的删除格数是一样的;只是中间谁占到哪个频次可能不同,答案总数不变。
如果用排序代替集合 used,怎么做?+
把所有频次从大到小排序,维护一个「当前允许的最大频次」上限:每个频次若超过上限就削到上限,削掉的差计入答案;若不超过上限,就把上限更新成这个频次。处理完当前频次后上限减 1,但最低降到 0。注意上限降到 0 后不能停:后面每个频次都只能削到 0,要把它的整个原值都加进答案,否则会漏算。它和集合写法结果一致,排序版多了排序的 O(A log A)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 字符频次唯一的最小删除次数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。