[LeetCode] Minimum Deletions to Make Character Frequencies Unique

 

 

Problem

 

 

---

 

Solution

 

Make a dictionary of all appearing alphabets and their frequencies.

Make a set of unique frequencies. Go through the dictionary and check if the frequency for this character already exists in the set. If it is, decrement the frequency until it is unique or reaches zero. Increment the counter at the same time. Add the frequency to the set.

 

My code exceeded the time limit at first. Issue was solved by turning the initial string iterative into a set when checking for frequencies.

 

 

class Solution(object):
    def minDeletions(self, s):
        """
        :type s: str
        :rtype: int
        """
        dict_al = {}
        count = 0
        for c in set(s):
            dict_al[c] = s.count(c)
        
        freq = set()
        for f in sorted(dict_al.values(), reverse = True):
            while f in freq and 0 < f:
                f -= 1
                count += 1
            freq.add(f)
            
        return count