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”.

The frequency of each letter refers to its frequency in the string s Is the number of times ,
To make a string s The frequency of each letter is different ,
If the frequency is the same , To delete letters and make them different in frequency , At least delete a few letters .

Ideas ：

I usually think of using hash map Record the number of times each letter appears , Then try to delete letters with the same frequency .
Because the letters only have 26 individual , So let's use a int Array representation hash map.

If the frequency is out of sequence , It will be much easier to handle , It only needs to vary each frequency from large to small 1 That's all ,
If the frequencies are equal, reduce the frequency to make their frequencies differ 1 above .

Note that if the frequencies are 0, There is no need to reduce the frequency , Because there is nothing to lose without this letter .

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;
}