1647. Make Character Frequencies Unique

1647. Make Character Frequencies Unique

Question

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.

Solution

数组统计+哈希表
用数组统计记录每个字符出现的数量。
count记录需要减少的字符数量。

遍历统计数组,如果哈希表中已经记录,则将数组统计减少,直到归零。
每减少一次则为count加一。
如果哈希表中未记录,则将当前数字添加到哈希表中。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int minDeletions(String s) {
int count = 0;
HashSet<Integer> set = new HashSet<>();
int[] bin = new int[26];
for(char c : s.toCharArray()){
bin[c - 'a']++;
}

for(int i = 0; i < 26; i++){
while(bin[i] !=0 && set.contains(bin[i])){
bin[i]--;
count++;
}
set.add(bin[i]);
}
return count;
}
}
Author

Xander

Posted on

2022-06-28

Updated on

2022-07-01

Licensed under

Comments