Leetcode-1647. 字符频次唯一的最小删除次数

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 <= 10e5s 仅含小写英文字母 思路（贪心）

1. 由于字符串只包含26个小写字母，因此，可以用一个大小为26的数组存放各个字母的频率2. 对数组里各个字母的频率进行排序（我们不需要知道具体是哪个字母的频率，不影响结果）3. 从频率高的往频率小的遍历，第一个频率不需要处理，从第二个开始，如果频率≥前一个，则需要调整成前一个的频率-1，并记录相应的操作次数。4. 如果前面一个字母的频率已经被调整成0了，则后面所有字母的频率都需要调整成0，直接累加后面所有字母的个数即可。5.如果当前字母的频率是0，则说明后面的字母频率全都是0，此时已经可以结束程序。 C++ Code

class Solution {
public:
    int minDeletions(string s) {
        vector freq(26,0);
        for(char x:s) freq[x-'a']++; //统计每个字符出现的频率
        sort(freq.begin(),freq.end());
        int count=0; //统计频次
        for(int i=24;i>=0;i--) //频率从高到低处理，且第一个字符不用处理
        {
            if(freq[i]==0) return count; //处理完毕
            if(freq[i+1]==0) //上一个字符频率已经是0了 后面的全都变成0
            {
                for(int j=0;j<=i;j++) count+=freq[j];
                return count;
            }
            if(freq[i]>=freq[i+1])
            {
                count+=freq[i]-freq[i+1]+1; //当前字符的频率调整成上一字符少一个
                freq[i]=freq[i+1]-1; 
            }

        }
        return count;

    }
};