P2801. 删除最少字符

解题思路

为了删除掉字符串 s 中出现次数最少的字符，我们必须先统计 s 中的所有字母的出现个数，很容易想到使用哈希表的 `Counter()` 来完成这个功能。

然后我们再统计哪些字母出现的次数为 最小出现次数，用一个哈希集合记录这些需要删除的字母，再使用字符串的 `replace()` 方法或者 `join()` 方法即可完成删除。

本题显然也是 哈希表 在统计元素频率类型的题目中的典型应用。

思路展开

参考代码分三步完成删除。第一步统计频率：遍历字符串 s 的每个字符，用哈希表 cnt 记录每种字符的出现次数，键是字符、值是次数。第二步确定要删谁：先在 cnt 的所有值里取最小值 minCnt，再把出现次数恰好等于 minCnt 的字符全部收进哈希集合 minCntSet。这里用集合而不是单个变量，正是为了落实题面“多个字符出现次数相同且都是最少，则全部删除”的规则。第三步重建字符串：按原顺序再遍历 s 一遍，凡是不在 minCntSet 里的字符依次追加到 StringBuilder 中，这样保留下来的字符相对顺序不变，等价于把待删字符从原串中抠掉。之所以第三步要靠哈希集合，是因为每个字符都要问一次“我该不该被删”，集合的平均 O(1) 查询让这一步保持线性。最后还有一个输出分支：如果删完后结果为空（例如所有字符出现次数都相同，全部被判定为最少而删光），参考代码按约定输出 empty。

复杂度分析

设字符串长度为 n，出现过的不同字符种数为 k（若只含小写字母则 k 不超过 26）。统计频率遍历一次 s，O(n)；求最小值和构建 minCntSet 各遍历一次 cnt，O(k)；重建字符串再遍历一次 s，每个字符做一次 O(1) 的集合查询，O(n)。总时间 O(n + k)，与字符串长度成正比。空间上 cnt 与 minCntSet 占 O(k)，结果串最长 O(n)。