具体思想:
主体思想是如何去除重复元素;
采用贪心思想:
1.可以使用去重set记录已经出现的频次,如果重复,就减到为零或者不再重复,讲新次数入set;
2.可以逆序排序。
从频次最高的开始遍历,如果当前频次和前一个频次相同,则-1,使其不同;
如果当前频次大于前一个平次,则说明当前频次和之前的频次发生重复,减到不再重复;
具体代码:
class Solution {
public:
int minDeletions(string s) {
vector<int>record(26,0);
for(int i=0;i<s.size();i++){
record[s[i]-'a']++;
}
set<int>cnt;
int count=0;
for(int i=0;i<26;i++){
if(record[i]>0){
int frec=record[i];
if(cnt.find(frec)!=cnt.end()){
frec--;
count++;
while(frec>0&&cnt.find(frec)!=cnt.end()){
frec--;
count++;
}
}
cnt.insert(frec);
}
}
return count;
}
};