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.The key idea in #1647 Minimum Deletions to Make Character Frequencies Unique is to ensure that no two characters in the string have the same frequency. Start by counting character occurrences using a hash map or frequency array. Once you have the counts, the challenge becomes adjusting them so each frequency is unique while minimizing deletions.
A common strategy is a greedy approach. Sort the frequencies in descending order and iterate through them while maintaining the maximum allowed frequency for the current character. If a frequency conflicts with a previously used value, reduce it (simulating deletions) until it becomes unique or reaches zero. Another variation uses a set to track already-used frequencies and repeatedly decreases conflicting values.
This greedy adjustment guarantees the minimum deletions because we only reduce frequencies when conflicts occur. The approach typically runs in O(n + k log k) time, where n is the string length and k is the number of distinct characters, with O(k) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting of Frequencies | O(n + k log k) | O(k) |
| Greedy with Hash Set for Used Frequencies | O(n + k^2) worst case | O(k) |
Fraz
Use these hints if you're stuck. Try solving on your own first.
As we can only delete characters, if we have multiple characters having the same frequency, we must decrease all the frequencies of them, except one.
Sort the alphabet characters by their frequencies non-increasingly.
Iterate on the alphabet characters, keep decreasing the frequency of the current character until it reaches a value that has not appeared before.
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.
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).
1def minDeletions(s: str) -> int:
2 from collections import Counter
3
4 freq = Counter(s)
5 used_freqs = set()
6 deletions = 0
7
8 for count in freq.values():
9 # Reduce the frequency until it is unique
10 while count > 0 and count in used_freqs:
11 count -= 1
12 deletions += 1
13 used_freqs.add(count)
14 return deletionsIn 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.
This approach uses a priority queue (or max heap) to manage frequencies, adjusting each frequency to maintain uniqueness from the highest to the lowest.
Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size.
1function minDeletions(s) {
2 const freq
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A greedy approach works because reducing frequencies only when conflicts occur guarantees the minimal number of deletions. By always keeping the highest possible valid frequency for each character, we avoid unnecessary removals and maintain optimality.
Yes, this problem reflects common interview themes like greedy decision making, frequency counting, and conflict resolution. Variants of this question have appeared in interviews at large tech companies because it tests algorithmic reasoning with strings and hash tables.
A hash map or frequency array is used to count characters efficiently. After that, a sorting structure or a hash set helps track used frequencies and enforce uniqueness. These structures make the greedy adjustment straightforward and efficient.
The optimal approach uses a greedy strategy. First count character frequencies, then sort them and reduce duplicates so each frequency becomes unique. By always decreasing the conflicting frequency to the next valid value, you minimize the total number of deletions.
The JavaScript solution mirrors the priority queue logic using a sorted array as a pseudo-max heap. The top element modification and reinserting after decrement mimics the behavior of a max heap.