leetcode 1647. Minimum Deletions to Make Character Frequencies Unique（所有字母频率不同的最小删除次数）_统计每个字母个数不同需要删除的字母最少数量

A string s is called good if there are no two different characters in s that have the same frequency.

Given a string s, return the minimum number of characters you need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string “aab”, the frequency of ‘a’ is 2, while the frequency of ‘b’ is 1.

Example 1:

Input: s = “aab”
Output: 0
Explanation: s is already good.
Example 2:

Input: s = “aaabbbcc”
Output: 2
Explanation: You can delete two 'b’s resulting in the good string “aaabcc”.
Another way it to delete one ‘b’ and one ‘c’ resulting in the good string “aaabbc”.

每个字母的频率指的是它在字符串s中出现的次数，
要让字符串s中每个字母的频率都不一样，
如果频率一样，要删除字母使它们频率不一样，至少要删几个字母。

思路：

一般会想到用hash map记录每个字母出现的次数，然后再想办法删掉频率一样的字母。
因为字母只有26个，所以用一个int数组代表hash map。

如果频率排过序，处理起来会方便很多，只需要从大到小每个频率相差1以上就行，
频率相等的就减频率使它们的频率相差1以上。

注意如果频率都是0，是不需要减频率的，因为都没有这个字母还减什么呢。

public int minDeletions(String s) {
    int[] cnt = new int[26];
    int cur = 0;
    int res = 0;
    
    for(char ch : s.toCharArray()) cnt[ch - 'a'] ++;
        
    Arrays.sort(cnt);
    
    cur = cnt[25];
    for(int i = 24; i >= 0; i --) {
        if(cnt[i] > cur - 1) {
            res += cnt[i] - Math.max(cur - 1, 0);
            cur --;
        } else {
            cur = cnt[i];
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20