1647. Minimum Deletions to Make Character Frequencies Unique

1647. Minimum Deletions to Make Character Frequencies Unique

Medium

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

Example 3:

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab".
Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters.

Accepted

95,827

Submissions

168,474

Solution :

Approach - Mapping:

1. Take a Set and Char[] to store used character and frequencies of characters respectively
2. Fill the freq array
3. Loop through 0 to 26, inner loop check while freq > 0 and !used.add(freq[i]) i.e. character is not used or added in set already that means freq already there we can't take another same freq.

4. So, collect the no of time we can't register a freq and also drop current freq by 1

Code: 

class Solution {
    public int minDeletions(String s) {
        Set<Integer> used = new HashSet<>();
        int[] freq = new int[26];
        int res = 0;
        for(char ch : s.toCharArray()) {
            freq[ch-'a']++;
        }
        System.out.println(Arrays.toString(freq));
        for (int i = 0; i < 26; ++i) {
            while (freq[i] > 0 && !used.add(freq[i])) {
                --freq[i];
                ++res;
            }
        }  
        return res;
    }
}

Space is O(1) and time is O(n).