题目描述

解题思路

这题不难想到需要统计每个字母的出现频率，一共有26个字母，故cnt数组有26维。我们可以枚举其中一种作为「删除操作结束后出现频率最低的字符」，将其设置为 c，那么所有频率小于 c 的字符都会被删除，所有频率大于 cnt[c]+k 的字符都会被删除至只剩下 cnt[c] 个。

首先可以证明 [删除操作结束后出现频率最低] 的那个字符的一定没有被删过，设这个字符为a，如果a被删过，说明一定是有比a频率更低的字符b与a的频率之差大于k了，那就算删a，最多删到与b频率相同，那此时就不会删b，满足b是频率最低的字符的情况，a永远不可能删到比b还低。

那么假设已经知道删除操作结束后频率最低的那个字母a了，那么计算删除操作的步骤为：

比a频率还低的字符全部删掉并统计次数：因为a已经是频率最低的字符了

比a频率大，且超过了k限制的字符，删到k限制以内，并统计次数。

总的统计次数加起来，就是删除操作数了。

然后依次遍历每个字母(最多26次)，计算当前字母为最终频率最低字母时的删除操作数，挑一个最小的即可。

代码

int minimumDeletions(string word, int k) {
	std::vector<int> freq(26,0);
	for(int i =0;i<word.size();i++)
	{
		freq[word[i] - 'a'] ++; 
	}
	std::sort(freq.begin(),freq.end());
	int use = -1,off = 0;
	for(int i = 0; i < 26; i++)
	{
		if(!freq[i])
		{
			off ++;
			continue;
		}
		int sum = 0;
		for(int q = off;q<26;q++)
		{
			if(freq[i] > freq[q]) sum += freq[q];
			else if(freq[q] > freq[i] + k) sum += freq[q] - freq[i] - k;
		}
		if(sum < use || use < 0)
		use = sum;
	}
	return use;
}