LeetCode 题解 | 1297.子串的最大出现次数
点击上方蓝字设为星标
下面开始今天的学习～
今天分享的题目来源于 LeetCode 第 1297 题：子串的最大出现次数。
题目描述
给你一个字符串 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^5
- 1 <= maxLetters <= 26
- 1 <= minSize <= maxSize <= min(26, s.length)
- s 只包含小写英文字母。
题目解析
给定一个字符串，找出出现次数最多的子串，但是有两个限制条件：
- 子串里面的不同的字符的个数不能超过 maxLetters
- 子串的长度必须在 minSize 和 maxSize 之间
这道题目，最初的想法就是使用 滑动窗口，但是这里有个问题，子串的长度既有上限也有下限，如果同时带着这两个限制条件去做滑动窗口，你会发现我们其实行不通。
举个例子，假如 minSize 是 3，maxSize 是 6，如果当前滑动窗口的大小是 4，而且子串里面不同字符的个数也不超过 maxLtters，也就是说两个限制条件均满足。
那么你是考虑移动左指针还是右指针？
仔细去想，如果按这种思路，其实窗口的两头并没有严格的限制条件去控制。
现在我们可以思考这样一个问题，是不是我们必须考虑 minSize 和 maxSize，还是说只用考虑其中一个？ 这道题目有一个很巧妙的地方在于，我们只需要考虑 minSize 即可，举个例子：
s = "aabcaabcaab", maxLetters = 2, minSize = 2, maxSize = 3
aab 出现次数最多，且满足限制条件
只要 aab 满足限制条件，它的子串 ab 也必定满足限制条件，且出现次数必定不低于 aab
参考代码
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<String, Integer> counts = new HashMap<>();
int n = s.length();
char[] sArr = s.toCharArray();
int[] hash = new int[26];
int l = 0, result = 0, unique = 0;
for (int r = 0; r < n; ++r) {
if (hash[sArr[r] - 'a']++ == 0) {
unique++;
}
// 如果条件不满足，移动左指针，缩小窗口，使条件满足
while (unique > maxLetters || r - l + 1 > minSize) {
if (hash[sArr[l++] - 'a']-- == 1) {
unique--;
}
}
// 条件满足，更新答案，这里只考虑 minSize
if (r - l + 1 == minSize) {
String cur = s.substring(l, r + 1);
counts.put(cur, counts.getOrDefault(cur, 0) + 1);
result = Math.max(result, counts.get(cur));
}
}
return result;
}
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-01-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
