Minimum Deletions To Make Character Frequencies Unique - Leetcode Solution

Problem Statement:

Given a string s consisting of n lowercase letters, you have to delete the minimum number of characters from s to make the frequency of each character unique. Return the minimum number of deletions needed.

Example: Input: s = "aab" Output: 0 Explanation: You will never get such a string after deleting any characters. Input: s = "aaabbbcc" Output: 2 Explanation: You can delete two 'b's resulting in the string "aaabcc". Now there aren't any repeating characters.

Solution Approach:

• Create a hashmap to count the frequency of all characters in the given string.
• Create a set to maintain the unique frequencies of characters in the hashmap.
• Iterate through the hashmap and check if the frequency of each character is unique. If not, calculate the number of deletions required to make it unique and add it to the answer.
• Return the answer.

Code:

class Solution { public: int minDeletions(string s) { unordered_map<char, int> freq_map; for(char ch: s) freq_map[ch]++; unordered_set<int> freq_set;

    int ans = 0;
    for(auto p: freq_map) {
        int freq = p.second;
        while(freq_set.count(freq)) {
            ans++;
            freq--;
        }
        if(freq > 0) freq_set.insert(freq);
    }
    return ans;
}

};

In the above code, we first create a frequency hashmap (freq_map) to store the count of each character in the string s.

We then create an unordered set (freq_set) to maintain a record of unique frequencies of all characters in the hashmap.

We then loop through each character in the hashmap and check if its frequency is unique or not. If the frequency is not unique, we calculate the number of deletions required to make it unique and add this to our answer (ans). We do this by reducing the frequency of the character until it becomes unique. This is done using the while loop.

Finally, if the frequency of the character is greater than 0, we insert this unique frequency into our set (freq_set).

The time complexity of the above code is O(n log n) since we need to perform deletion, which in the worst case may take O(n log n) time.

1