Minimum Deletions to Make Character Frequencies Unique

How it works

By sorting frequencies in descending order, we process them from highest to lowest. We track the maximum allowed frequency for the next character. If a frequency exceeds this limit, we delete down to the limit. After each character, the next allowed frequency decreases by one (minimum 0). This ensures all final frequencies are distinct.

Steps

1. Count character frequencies and sort in descending order.
2. Set maxAllowedFreq to the highest frequency.
3. For each frequency:
   • If it exceeds maxAllowedFreq, add the difference to deletions.
   • Update maxAllowedFreq to max(0, current_frequency - 1).
4. Return the total deletion count.

Complexity

• Time complexity: O(n + m log m)
• Space complexity: O(m)

Where n is the length of the string s and m is the total number of unique frequncies possible.

Things to watch for

Adding Zero Frequencies to the Used Set

When a frequency is decremented to zero, adding it to the used frequency set prevents other characters from also being reduced to zero. Multiple characters can validly have frequency zero (meaning they are completely deleted), so zero should either not be added or handled specially.

Not Decrementing Until an Available Slot is Found

Some implementations only check if a frequency is taken and decrement once. The correct approach requires a while loop that continues decrementing until finding an unused frequency or reaching zero. A single decrement may land on another taken frequency.

Counting Characters Instead of Frequencies

The problem asks for minimum deletions to make frequencies unique, not to make characters unique. Confusing the two leads to counting unique characters or deleting entire character types rather than reducing specific frequency counts.

class Solution:
    def minDeletions(self, s: str) -> int:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1

        count.sort(reverse=True)
        res = 0
        maxAllowedFreq = count[0]

        for freq in count:
            if freq > maxAllowedFreq:
                res += freq - maxAllowedFreq
                freq = maxAllowedFreq
            maxAllowedFreq = max(0, freq - 1)

        return res

class Solution {
public:
    int minDeletions(string s) {
        vector<int> count(26, 0);
        for (char& c : s) {
            count[c - 'a']++;
        }

        sort(count.begin(), count.end(), greater<int>());
        int res = 0;
        int maxAllowedFreq = count[0];

        for (int& freq : count) {
            if (freq > maxAllowedFreq) {
                res += freq - maxAllowedFreq;
                freq = maxAllowedFreq;
            }
            maxAllowedFreq = max(0, freq - 1);
        }

        return res;
    }
};