LC-1647. 字符频次唯一的最小删除次数（哈希+计数）

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

难度中等56

如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。

给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。

字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。

示例 1：

输入：s = "aab"
输出：0
解释：s 已经是优质字符串。

示例 2：

输入：s = "aaabbbcc"
输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。

示例 3：

输入：s = "ceabaacb"
输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）

提示：

• 1 <= s.length <= 105
• s 仅含小写英文字母

哈希+计数

哈希计数，统计每个字符串的数量。
在重复的情况下，减1试重

class Solution {public int minDeletions(String s) {int[] cnt = new int[26];for(char c : s.toCharArray()){cnt[c - 'a']++;}int res = 0;Set<Integer> set = new HashSet<>();for(int i = 0; i < cnt.length; i++){int cur = cnt[i];while(cur != 0 && !set.add(cur)){cur--;res++;}}return res;}
}

[简单] 242. 有效的字母异位词【哈希表】【字符串】【排序】【计数】[哈希表 + 计数] [242. 有效的字母异位词]

[简单] 409. 最长回文串【贪心】【哈希表】【字符串】[贪心 哈希表 计数 回文] [409. 最长回文串]

[简单] 819. 最常见的单词【哈希表】【字符串】【计数】[哈希表 + 计数] [819. 最常见的单词]

[简单] 1189. “气球” 的最大数量【哈希表】【字符串】【计数】[哈希表] [1189. “气球” 的最大数量]

[简单] 1252. 奇数值单元格的数目【数学】【模拟】【哈希表】[哈希表 数学] [1252. 奇数值单元格的数目]

[中等] 1347. 制造字母异位词的最小步骤数【哈希表】【计数器】[哈希表 计数器] [1347. 制造字母异位词的最小步骤数]

[中等] 1647. 字符频次唯一的最小删除次数【贪心】【字符串】【排序】[哈希计数] [1647. 字符频次唯一的最小删除次数]

[中等] 1743. 从相邻元素对还原数组【哈希表】[哈希表] [1743. 从相邻元素对还原数组]

[中等] 1887. 使数组元素相等的减少操作次数【数组】【排序】[哈希表 + 计数] [1887. 使数组元素相等的减少操作次数]

[中等] 2131. 连接两字母单词得到的最长回文串【贪心】【数组】【哈希表】【字符串】【计数】[贪心 哈希表 计数] [2131. 连接两字母单词得到的最长回文串]

[中等] 2150. 找出数组中的所有孤独数字【数组】【哈希表】【计数】[哈希 计数] [2150. 找出数组中的所有孤独数字]

[中等] 2186. 使两字符串互为字母异位词的最少步骤数【哈希表】【计数】【字符串】[哈希 + 计数] [2186. 使两字符串互为字母异位词的最少步骤数]