Watch 10 video solutions for Minimum Deletions to Make Character Frequencies Unique, a medium level problem involving Hash Table, String, Greedy. This walkthrough by Fraz has 16,117 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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".
Example 3:
Input: s = "ceabaacb" Output: 2 Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).
Constraints:
1 <= s.length <= 105s contains only lowercase English letters.Problem Overview: Given a string s, delete the minimum number of characters so that no two characters share the same frequency. After deletions, each remaining character count must be unique.
Approach 1: Frequency Array + Set (Greedy) (Time: O(n + k log k), Space: O(k))
Count how many times each character appears using a frequency array or a hash table. Sort or iterate through the frequencies and keep a set of frequencies already used. If a frequency is already present in the set, repeatedly decrement it (simulate deleting characters) until the value becomes zero or unique. Each decrement represents one deletion. This works because the greedy rule is simple: always keep the highest possible frequency that has not been used yet. The approach is efficient since the alphabet size (k) is small compared to the string length.
The key insight: reducing a frequency by one is always the best local move when a conflict occurs. Larger frequencies should be preserved as much as possible while pushing duplicates downward until they reach an unused value.
Approach 2: Priority Queue for Frequency Management (Time: O(n + k log k), Space: O(k))
Insert all character frequencies into a max heap (priority queue). Continuously compare the largest frequency with the next largest. If both are equal, decrement the top value and push it back into the heap if it remains greater than zero. Each decrement corresponds to deleting a character from that group. The heap ensures you always resolve conflicts starting from the highest counts.
This approach explicitly models the frequency ordering using a heap instead of sorting. It’s a natural fit when working with dynamic frequency adjustments and demonstrates understanding of greedy conflict resolution combined with sorting-like ordering behavior.
Recommended for interviews: The Frequency Array + Set greedy approach is typically expected. It is shorter, easier to reason about, and uses constant-size alphabet assumptions effectively. The priority queue method is slightly heavier but still valid and demonstrates good command of heaps and frequency management.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Array + Set (Greedy) | O(n + k log k) | O(k) | Best general solution when alphabet size is small and you want simple greedy logic |
| Priority Queue (Max Heap) | O(n + k log k) | O(k) | Useful when modeling conflicts dynamically with heaps or when practicing priority queue patterns |