【前缀和】100255. 成为 K 特殊字符串需要删除的最少字符数

本文涉及知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
枚举

LeetCode100255. 成为 K 特殊字符串需要删除的最少字符数

给你一个字符串 word 和一个整数 k。
如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j 都成立，则认为 word 是 k 特殊字符串。
此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。
返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。
示例 1：

输入：word = “aabcaba”, k = 0

输出：3

解释：可以删除 2 个 “a” 和 1 个 “c” 使 word 成为 0 特殊字符串。word 变为 “baba”，此时 freq(‘a’) == freq(‘b’) == 2。

示例 2：

输入：word = “dabdcbdcdcd”, k = 2

输出：2

解释：可以删除 1 个 “a” 和 1 个 “d” 使 word 成为 2 特殊字符串。word 变为 “bdcbdcdcd”，此时 freq(‘b’) == 2，freq(‘c’) == 3，freq(‘d’) == 4。

示例 3：

输入：word = “aaabaaa”, k = 2

输出：1

解释：可以删除 1 个 “b” 使 word 成为 2特殊字符串。因此，word 变为 “aaaaaa”，此时每个字母的频率都是 6。

提示：
1 <= word.length <= 10⁵
0 <= k <= 10⁵
word 仅由小写英文字母组成。

大致思路

用cnt记录个字符出现的次数，并排序。
枚举[cnt[i],ctn[j]) 保留，[0,cnt[i])全删除，[ctn[j],26) 删除到 cnt[i]+k 。
可以用前缀和，也可以暴力。

代码

class Solution {
public:
	int minimumDeletions(string word, int k) {
		int cnt[26] = { 0 };
		for (const auto& ch : word)
		{
			cnt[ch - 'a']++;
		}
		sort(cnt, cnt + 26);
		int iDel = word.length();
		int iSum = 0;
		for (int i = 0; i < 26; i++)
		{
			int j = i+1;
			for (; (j < 26) && (cnt[j] - cnt[i] <= k); j++);
			//保留[i,j) 
			int iCurDel = iSum;
			for (int j1 = j ; j1 < 26; j1++)
			{
				iCurDel += cnt[j1] - (cnt[i]+k);
			}
			iDel = min(iDel, iCurDel);
			iSum += cnt[i];
		}
		return iDel;
	}
};

测试用例

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}
int main()
{

	str
	ing word;
	int k;
	{
		word = "ahahnhahhah"; k = 1;
		auto res = Solution().minimumDeletions(word, k);
		Assert(2, res);
	}

}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。