05 August 2008
如果字符串 s 中不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 “aab” 中，’a’ 的频次是 2，而 ‘b’ 的频次是 1 。
示例 1：
1
2
3
输入：s = "aab"
输出：0
解释：s 已经是优质字符串。
示例 2：
1
2
3
4
输入：s = "aaabbbcc"
输出：2
解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。
示例 3：
1
2
3
4
输入：s = "ceabaacb"
输出：2
解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
提示：
1
2
1 <= s.length <= 105
s 仅含小写英文字母
贪心思想：统计+去重，不需要排序
首先统计各个字母的出现个数，再使用HashSet进行去重。 HashSet中保存不同的数目，如果加进来的数目已经存在，就自减，减到HashSet中没有的数目
为什么不用排序？例如添加顺序为4 4 3 2 1和3 2 1 4 4， 第一种是把4 3 2 1每个数都减1，答案为4。 第二种是直接把最后一个4减到0，答案也是4. 所以答案只需要在乎去重自减时，减少的个数，而不用在意顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int minDeletions(String s) {
int[] a = new int[26];
char[] cs = s.toCharArray();
for (char c : cs) a[c - 'a'] ++;// 统计字母个数
Set<Integer> h = new HashSet<Integer>();
int res = 0;
for (int i : a) {
if (i != 0) { // 有数目才进行判断
while (h.contains(i)) { // set已经包含就自减
i --;
res ++;
}
if (i != 0) h.add(i); // 自减到0时，表示完全删除了某个字母，不能加入set中
}
}
return res;
}
}