Minimum Deletions to Make Character Frequencies Unique

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

Constraints:

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

A simple Leetcode question. Lets start.

We have to make frequencies of all the letters unique. So first we need to know the current frequencies of all the letters. I used a dictionary in python to get the count but using collections counter was way faster so we will use that here with dictionary code commented. Next we need to check while iterating on the the frequencies if we have already encountered that frequency or not so we will maintain a set. If we have seen the frequency, then keep on decreasing the value of frequency until it’s unique or 0 and keep on adding the deletion count. Finally return the deletion count. Here’s the code:

def minDeletions(s):
        # freq_map = {}
        # for i in s:
        #     if i not in freq_map:
        #         freq_map[i] = 0
        #     freq_map[i] += 1
        # freq = set()
        freq_map, m, freq = collections.Counter(s), 0, set() # using same thing but inbuilt is faster, way faster
        m = 0
        for i in freq_map.values():
            if i not in freq: freq.add(i)
            else:
                while i in freq and i > 0:
                    i -= 1
                    m += 1
                freq.add(i)
        return m

Thats all. Please comment if you have any questions. Thanks.