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.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.
Java
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.
JavaScript
Time Complexity: O(N log N) due to priority queue operations. Space Complexity: O(1), constrained space regarding character set size.
| 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. |
Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique • Fraz • 15,951 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