Minimum Deletions to Make Character Frequencies Unique — Solution

Problem

Given a string, determine the fewest characters you need to delete so that no two distinct characters appear the same number of times. A string is "good" when every character has a unique frequency.

• Input: s = "aaabbbcc"
• Output: 2
• Explanation: Frequencies are a=3, b=3, c=2. Delete one 'b' (b→2) and one 'c' (c→1) so frequencies become {3, 2, 1} — all distinct.

For s = "aab", frequencies are a=2, b=1 — already all distinct, so the answer is 0.

Intuition

The key observation is that you can only delete characters, not add them, so a frequency can only decrease. Greedily processing the largest frequencies first and "parking" each one at the highest available slot minimizes total deletions — reducing a large frequency to a smaller unused slot costs fewer deletions than the reverse order would.

Solution — Greedy with Sorted Frequencies

Sort character frequencies in descending order, then assign each to the highest slot it can occupy without conflicting with an already-used frequency.

1. Count the frequency of every character in the string.
2. Collect those frequencies into a list and sort it in descending order.
3. Maintain a set of frequencies that are already "taken."
4. For each frequency, decrement it (counting each step as one deletion) until it lands on an unused slot or hits zero.
5. If the final value is above zero, mark that slot as taken.
6. Return the total deletion count.

1from collections import Counter
2
3def min_deletions(s: str) -> int:
4    frequencies = sorted(Counter(s).values(), reverse=True)  # largest first
5    used_frequencies = set()
6    deletions = 0
7
8    for freq in frequencies:
9        while freq > 0 and freq in used_frequencies:
10            freq -= 1       # each decrement removes one character
11            deletions += 1
12        if freq > 0:
13            used_frequencies.add(freq)
14
15    return deletions

Time: O(n) — counting is O(n); sorting ≤ 26 frequencies is O(1); the total number of decrements across all frequencies is bounded by n since each decrement represents one deletion and you can't delete more characters than exist.

Space: O(1) — the frequency array and used-frequencies set hold at most 26 entries, independent of input length.

Complexity Summary

Common Mistakes

• Using a list instead of a set for used_frequencies — a linear scan to check membership makes the total cost O(n · k) when k frequencies need many decrements.
• Not stopping the while loop at zero — a frequency of 0 means the character is fully removed and must not be added to the used set; continuing past 0 would count phantom deletions.
• Processing frequencies in ascending order — that approach greedily forces small frequencies into even smaller slots and inflates the deletion count unnecessarily.
• Counting the final reduced value as the deletions — the number of deletions is the difference between the original frequency and the final slot, not the slot value itself.
• Assuming at most one decrement per frequency — "aaabbbccc" has frequencies [3, 3, 3]; the third one must decrement twice (3→2→1), producing 2 deletions just for that character.

Related Problems

• sort-characters-by-frequency — sorts characters by descending frequency, the same counting pattern
• reorganize-string — ensures no two adjacent identical characters using a frequency-based greedy
• top-k-frequent-elements — selects the k characters with the highest frequency, same counting foundation
• top-k-frequent-words — frequency ranking with lexicographic tiebreaking
• first-unique-character-in-a-string — finds the character whose frequency equals exactly 1