网站建设在哪能看,二元期权网站建设,杨庄网站建设,宜昌永东建设网站文章目录1. 题目2. 解题1. 题目
如果字符串 s 中 不存在 两个不同字符 频次 相同的情况#xff0c;就称 s 是 优质字符串 。
给你一个字符串 s#xff0c;返回使 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 10^5
s 仅含小写英文字母来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-deletions-to-make-character-frequencies-unique 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
从大的频数往下找找到一个没有在频数集合里出现的频数
class Solution {
public:int minDeletions(string s) {unordered_mapint,int m;for(char c : s)m[c];//字符计数vectorint num;for(auto mi : m)num.push_back(mi.second);//频数sort(num.begin(), num.end());//频数排序setint set;int del 0;for(int i num.size()-1; i0; --i){ // 从大的频数开始遍历if(!set.count(num[i]))set.insert(num[i]);//频数不存在直接插入setelse//频数存在往下找不存在的频数{int k num[i]-1;while(set.count(k))k--;//找到一个 频数 k 是没有出现过的if(k 0)//如果频数大于 0set.insert(k);del min(num[i], num[i]-k);//要删除的字符数}}return del;}
};256 ms 17.7 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
