题目大意：
子串的最大出现次数
给你一个字符串 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 只包含小写英文字母。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1297
解题思路分析：
说实话一开始就没有想到太好的解题思路，尝试了一下暴力解法，居然可以通过，并且效率还不算太低。暴力解即以单词的每一位为开头取出长度为 minSize 到 maxSize 的所有子串，如果子串中的字母种类个数小于等于 maxLetters ，则将该子串加入到map中计数，循环玩所有子串之后，找到map中计数最大的一个即是返回结果。暴力解的时间复杂度为：O(n*26)，n为字符串长度。
为了精益求精，接下来我们需要对暴力解进行剪枝优化，优化的关键点在于 minSize 和 maxSize ，比如最小长度为2，最大长度为5时，对于字符串abbbb来说，ab，abb，abbb，abbbb都是合理子串，但我们只要找到第一个（最短的）合理子串即可。因为abbbb包含了ab，如果整个字符串中存在N个abbbb，那么肯定至少包含了N个ab，也就是说，较短的子串个数一定大于等于较长的子串个数。
实现代码：
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
// 统计每个子串出现的个数
Map<String, Integer> map = new HashMap<>();
int res=0; // 返回结果
// 以每一个index开头循环
for(int i=0;i<s.length();i++){
// 当前子串长度
int length=0;
// 当前子串中字母种类个数
int letterCount=0;
// 记录出现过的字母
boolean[] hasLetter = new boolean[26];
// 当前子串
StringBuilder sb = new StringBuilder();
// 循环所有以i开头的子串
for(int j=i;j<s.length();j++){
length++; // 子串长度加一
char c = s.charAt(j); // 当前字符
sb.append(c); // 当前子串
// 如果当前字符在当前子串中没有出现过
if(!hasLetter[c-'a']){
// 标记为出现过
hasLetter[c-'a']=true;
// 字母种类个数加一
letterCount++;
// 如果字母种类个数大于maxLetters，退出当前循环
if(letterCount>maxLetters) break;
}
// 当子串长度大于等于minSize时（满足条件的子串）
if(length>=minSize){
// 更新当前子串出现的次数
int count = map.getOrDefault(sb.toString(),0)+1;
map.put(sb.toString(), count);
// 更新全局子串出现的最大次数
res=Math.max(res, count);
// 找到当前最短子串后，可退出循环。原因参考上文分析
break;
}
// 如果子串长度等于最大长度，退出循环
if(length==maxSize) break;
}
}
return res;
}本题解法执行时间为46ms。
Runtime: 46 ms, faster than 83.87% of Java online submissions for Maximum Number of Occurrences of a Substring.
Memory Usage: 40.7 MB, less than 100.00% of Java online submissions for Maximum Number of Occurrences of a Substring.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1297-maximum-number-of-occurrences-of-a-substring-解题思路分析/