1647. Minimum Deletions to Make Character Frequencies Unique

Problem Statement

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.

Intuition

Approach 1: Space N, Time N

iteratively delete the count of frequencies in the map,
Till it becomes 0, or we are not able to find in map


Approach 2: Space 1, Time N

Sort according to freq
1 2 2 3 3
Now come from last,
Make second last as 2
The third last one less than second last
So on in array till we reach zero

Links

https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/description/?envType=daily-question&envId=2023-09-12

Video Links

https://www.youtube.com/watch?v=sq7LBb6Kd3g&ab_channel=AryanMittal

Approach 1:

Space taken

C++

class Solution {
public:
    int minDeletions(string s) {
        unordered_map<char,int> freq;
        unordered_map<int,int> count;
        for(auto &c: s)
            freq[c]++;

        for(auto &it: freq)
            count[it.second]++;
        
        int ans=0;
        for(auto &it: count){
            if(it.second == 1)
                continue;

            while(it.second!=1) {
                it.second--;
                int val = it.first;
                int ct = 0;

                while(count.find(val) != count.end()){
                    val--;
                    ct++;
                }

                if(val != 0)
                    count[val]++;

                ans+=ct;
            }
        }

        return ans;
    }
};

Approach 2:

Without space

C++

class Solution {
public:
    int minDeletions(string s) {
        //Array to store the count of each character.
        vector<int> freq (26, 0);
        
        //Calculatimg frequency of all characters.
        for (char c : s){
            freq[c - 'a']++;
        }
        
        //sorting the frequencies. So the greatest frequencies are in right side.
        sort(freq.begin(), freq.end());
        
        int del = 0; //to store the deletions.
        
        //Checking if 2 frequencies are same, if same then decrease the frequency so that it becomes less than the next greater one.So Start from the 2nd greatest frequency that is at freq[24].
        for (int i = 24; i >= 0; i--) {
            
            if(freq[i] == 0) break; // if frequency is 0 that means no more character is left.
            
            if(freq[i] >= freq[i+1]){
                int prev = freq[i]; //To store the frequency before deletion.
                freq[i] = max(0, freq[i+1] -1); //New frequency should be 1 less than the previous frequency in the array.
                del += prev - freq[i]; //Calculating deleted characters 
            }
        }
        return del;
    }
};

Approach 3:

C++

Approach 4:

C++