【C++滑动窗口】1297. 子串的最大出现次数|1748

本文涉及的基础知识点

C++算法：滑动窗口及双指针总结 固定长度滑动窗口

LeetCode1297. 子串的最大出现次数

给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。
示例 1：
输入：s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 “aab” 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。
示例 2：
输入：s = “aaaa”, maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 “aaa” 在原字符串中出现了 2 次，且它们有重叠部分。
示例 3：
输入：s = “aabcabcab”, maxLetters = 2, minSize = 2, maxSize = 3
输出：3
示例 4：
输入：s = “abcde”, maxLetters = 2, minSize = 3, maxSize = 3
输出：0
提示：
1 <= s.length <= 10⁵
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s 只包含小写英文字母。

滑动窗口

令符合条件的最长串为s，如果s.length > minSize，则s.substr(0,minSize)也是最优解。故只需要枚举长度为minSize的子串。
直接用哈希映射mCnt， mCnt[s.substr(i,minSize)]的时间复杂度是：O(n minSize)，操作 哈希的时间复杂度大约是O(7)，所以勉强能过。
用带数量的字典树，数据复杂度是O(n minSize)
如果有滚动哈希的封装类，使用滚动哈希，时间复杂度是O(n)。

代码

核心代码

class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
int cnt[26] = { 0 };
int charCnt = 0;
int i = 0;
for (; i < minSize; i++) {
auto& tmp = cnt[s[i] - 'a'];
tmp++;
charCnt += (1 == tmp);
}
unordered_map<string, int> mCnt;
if (charCnt <= maxLetters) { mCnt[s.substr(i - minSize, minSize)]++; }
for (; i < s.length(); i++) {
auto& tmp = cnt[s[i] - 'a'];
tmp++;
charCnt += (1 == tmp);
auto& tmp1 = cnt[s[i - minSize] - 'a'];
tmp1--;
charCnt -= (0 == tmp1);
if (charCnt <= maxLetters) { mCnt[s.substr(i+1 - minSize, minSize)]++; }
}
int ans = 0;
for (const auto& [tmp, maxCnt] : mCnt) {
ans = max(ans, maxCnt);
}
return ans;
}
};

单元测试

string s;
int maxLetters,  minSize,  maxSize;
TEST_METHOD(TestMethod1)
{
s = "abcd", maxLetters = 2, minSize = 1, maxSize = 2;
auto res = Solution().maxFreq(s, maxLetters, minSize, maxSize);
AssertEx(1, res);
}
TEST_METHOD(TestMethod11)
{
s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4;
auto res = Solution().maxFreq(s, maxLetters, minSize, maxSize);
AssertEx(2, res);
}
TEST_METHOD(TestMethod12)
{
s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3;
auto res = Solution().maxFreq(s, maxLetters, minSize, maxSize);
AssertEx(2, res);
}
TEST_METHOD(TestMethod13)
{
s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3;
auto res = Solution().maxFreq(s, maxLetters, minSize, maxSize);
AssertEx(3, res);
}
TEST_METHOD(TestMethod14)
{
s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3;
auto res = Solution().maxFreq(s, maxLetters, minSize, maxSize);
AssertEx(0, res);
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

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

原文地址：https://blog.csdn.net/he_zhidan/article/details/142626261

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！