class Solution {
public:
int minDeletions(string s) {
}
};
1647. 字符频次唯一的最小删除次数
如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。
示例 1：
输入：s = "aab"
输出：0
解释：s 已经是优质字符串。
示例 2：
输入：s = "aaabbbcc" 输出：2 解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。 另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。
示例 3：
输入：s = "ceabaacb" 输出：2 解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。 注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
提示：
1 <= s.length <= 105s 仅含小写英文字母原站题解
cpp 解法, 执行用时: 40 ms, 内存消耗: 16.9 MB, 提交时间: 2022-12-11 12:52:43
class Solution {
public:
int minDeletions(string s) {
vector<int>a(26);
for(char c:s) a[c-'a']++;
sort(a.begin(),a.end());
int count=0;
for(int i=24;i>=0;i--){
if(a[i]!=0&&a[i]>=a[i+1]){
int temp=a[i];
a[i]=a[i+1]==0?0:a[i+1]-1;
count+=temp-a[i];
}
}
return count;
}
};
cpp 解法, 执行用时: 52 ms, 内存消耗: 16.8 MB, 提交时间: 2022-12-11 12:52:07
/**
* 因为只能通过去掉字符来减小出现次数，因此出现次数较多的字符应当「尽可能保留」，
* 以免和后面「撞车」，这就是本题的贪心思路。
* 首先得到每个字符出现的次数，并从大到小排序。然后从前到后，遍历这个频数数组。
**/
class Solution {
public:
int minDeletions(string s) {
vector<int> cnt(26, 0);
for (auto ch: s) {
cnt[ch - 'a']++;
}
sort(cnt.begin(), cnt.end(), greater<int>());
int ret = 0;
int prev = cnt[0];
for (int i = 1; i < 26 && cnt[i] > 0; i++) {
if (prev <= cnt[i]) {
prev = max(prev - 1, 0);
ret += (cnt[i] - prev);
} else {
prev = cnt[i];
}
}
return ret;
}
};
java 解法, 执行用时: 6 ms, 内存消耗: 41.9 MB, 提交时间: 2022-12-11 12:51:08
/**
* 首先统计各个字母的出现个数，再使用HashSet进行去重。
* HashSet中保存不同的数目，如果加进来的数目已经存在，就自减，减到HashSet中没有的数目
**/
class Solution {
public int minDeletions(String s) {
int[] a = new int[26];
char[] cs = s.toCharArray();
for (char c : cs) a[c - 'a'] ++;// 统计字母个数
Set<Integer> h = new HashSet<Integer>();
int res = 0;
for (int i : a) {
if (i != 0) { // 有数目才进行判断
while (h.contains(i)) { // set已经包含就自减
i --;
res ++;
}
if (i != 0) h.add(i); // 自减到0时，表示完全删除了某个字母，不能加入set中
}
}
return res;
}
}