Minimum Deletions to Make Character Frequencies Unique | Leetcode 1647

 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.

solutions : 

The problem at hand is to determine the minimum number of deletions required to make a given string balanced. A string is considered balanced when all characters occur an equal number of times.

The Solution: Our C++ solution employs two unordered maps, map1 and map2, to achieve this task efficiently. Let's break down the key components of the solution:

Frequency Counting: We start by iterating through the input string s and populate map1 with the frequency of each character. This map will help us keep track of how many times each character appears in the string.

Finding the Maximum Frequency: We find the maximum frequency of any character in the string, which is crucial for our optimization later.

Initializing map2: We create map2 with size equal to the maximum frequency found. This map will store characters corresponding to their frequency. Initially, all values in map2 are set to '#'.

Counting Deletions: The core of our solution is in this step. We iterate through map1 again, checking if the current character's frequency in map2 is already occupied. If it is, we enter a loop to find the next available frequency slot (marked with '#'), decreasing the frequency until we find an available slot.

Returning the Result: Finally, we return the count variable, which holds the minimum number of deletions required to balance the string.

Here is the complete code :

class Solution { public:     int minDeletions(string s) {         unordered_map<char , int>map1;         unordered_map<int , char>map2;         int size = s.length();         for(int i =0 ; i  < size ; i++)         {             map1[s[i]]++;         }         int max = INT_MIN;         for(auto &x : map1)         {             int a = x.second;             if(max < a)             {                 max = a;             }         }         for(int i =0 ; i <= max ; i++)         {             map2[i] ='#';         }         int count =0;         for(auto &x : map1)         {             char a = x.first;             int b = x.second;             if(map2[x.second] == '#')             {                 map2[x.second] = x.first;             }             else             {                 while(map2[map1[a]] != '#' && map1[a] != 0)                 {                      // x.second -= 1;                     map1[a]--;                     count++;                                         }                 if(map2[map1[a]] == '#' )                 {                     map2[map1[a]] = a;                 }             }         }         return count;           } };