Minimum Deletions to Make Character Frequencies Unique
Medium · Greedy · Hash Table · String · Greedy · Sorting
Problem
A string is good when no two different letters in it appear the same number of times. A letter that no longer appears has frequency 0 and is ignored.
Given a string s, return the fewest characters you must delete to make s good.
Examples
Input: s = "aaabbc" Output: 0
The counts 3, 2 and 1 are already different.
Input: s = "xxyyzz" Output: 3
Keep one letter at 2, lower another to 1 (one deletion) and remove the third entirely (two deletions).
Input: s = "ppppqqqq" Output: 1
Delete one q so the counts become 4 and 3.
Constraints
- 1 <= len(s) <= 10^5
- s contains only lowercase English letters
Approaches
- Baseline: step each count down until it is free — time O(n + k²), space O(k)
Follow-up
If adding letters were allowed as well as deleting them, a count could also move up to a free value, and the cheapest fix for each tie is the nearer free value on either side. If every count must instead be equal, try each existing count as the common target (see the use case "Delete letters until every count is equal").
Related problems
Start free on Cariara · Coding problems · System design studio
