題目描述

解題思路

這題不難想到需要統計每個字母的出現頻率，一共有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;
}