LeetCode 1647. Minimum deletion times of unique character frequency

1647. Character frequency the minimum number of deletions that are unique

If the string s in non-existent Two different characters The frequency of The same thing , It's called s yes High quality string .

Give you a string s, Return to make s Become High quality string Need to delete Minimum Number of characters .

Of characters in a string The frequency of Is the number of occurrences of this character in the string . for example , In string "aab" in ,'a' The frequency of 2, and 'b' The frequency of 1 .

Example 1：

 Input ：s = "aab"
 Output ：0
 explain ：s  It is already a high-quality string .

Example 2：

 Input ：s = "aaabbbcc"
 Output ：2
 explain ： You can delete two  'b' ,  Get a good string  "aaabcc" .
 Another way is to delete a  'b'  And a  'c' , Get a good string  "aaabbc" .

Example 3：

 Input ：s = "ceabaacb"
 Output ：2
 explain ： You can delete two  'c'  Get a good string  "eabaab" .
 Be careful , Just focus on the characters that still exist in the result string .（ namely , The frequency is  0  Characters are ignored .）

Tips ：

• 1 <= s.length <= 105
• s Small letters only

Two 、 Method 1

Hash + greedy

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

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(n).