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.
This approach involves using a frequency array to count the number of times each character appears. We then use a set to track frequencies that we have already seen, and decrement frequencies until they are unique.
In this implementation, we use Python's Counter from the collections module to count character frequencies. We also maintain a set to keep track of unique frequencies we have seen. For each character frequency, if it's already in the set, we decrement the frequency until it's unique.
Time Complexity: O(N), where N is the length of the string. Space Complexity: O(1) because the number of unique characters is limited (26 lowercase English letters).
This approach uses a priority queue (or max heap) to manage frequencies, adjusting each frequency to maintain uniqueness from the highest to the lowest.
In this C++ solution, we first compute frequency counts in a vector. We then use a priority queue to keep higher frequencies at the top. When consecutive top elements (frequencies) are the same, we decrement and push back to keep them unique, counting deletions.
C++
JavaScript
Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size.
First, we use an array cnt of length 26 to count the occurrences of each letter in the string s.
Then, we sort the array cnt in descending order. We define a variable pre to record the current number of occurrences of the letter.
Next, we traverse each element v in the array cnt. If the current pre is 0, we directly add v to the answer. Otherwise, if v geq pre, we add v - pre + 1 to the answer and decrement pre by 1. Otherwise, we directly update pre to v. Then, we continue to the next element.
After traversing, we return the answer.
The time complexity is O(n + |\Sigma| times log |\Sigma|), and the space complexity is O(|\Sigma|). Here, n is the length of the string s, and |\Sigma| is the size of the alphabet. In this problem, |\Sigma| = 26.
| Approach | Complexity |
|---|---|
| Using Frequency Array and Set | Time Complexity: O(N), where N is the length of the string. Space Complexity: O(1) because the number of unique characters is limited (26 lowercase English letters). |
| Priority Queue for Frequency Management | Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size. |
| Array + Sorting | — |
| Default Approach | — |
| 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 |
Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique • Fraz • 16,117 views views
Watch 9 more video solutions →Practice Minimum Deletions to Make Character Frequencies Unique with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor