https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/
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 <= 105
s contains only lowercase English letters.
- code
class Solution {
public int minDeletions(String s) {
HashMap<Character, Integer> freq = new HashMap<>();
HashSet<Integer> seen = new HashSet<>();
for (char c: s.toCharArray()){
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
int countToDelete = 0;
for (char c: freq.keySet()){
int curFreq = freq.get(c);
if (!seen.contains(curFreq)){
seen.add(curFreq);
}else{ // delete to make it not in seen
while (seen.contains(curFreq) && curFreq >= 1){
curFreq--;
countToDelete++;
}
seen.add(curFreq);
}
}
return countToDelete;
}
}
- code
class Solution {
public int minDeletions(String s) {
int[] frequency = new int[26];
for (int i = 0; i < s.length(); i++) {
frequency[s.charAt(i) - 'a']++;
}
Arrays.sort(frequency);
int deleteCount = 0;
int maxFreqAllowed = s.length();
for (int i = 25; i >= 0 && frequency[i] > 0; i--) {
if (frequency[i] > maxFreqAllowed) {
deleteCount += frequency[i] - maxFreqAllowed;
frequency[i] = maxFreqAllowed;
}
maxFreqAllowed = Math.max(0, frequency[i] - 1);
}
return deleteCount;
}
}