# 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 只包含小写英文字母。
```
## 前置知识
* 字符串
* 滑动窗口
## 暴力法
题目给的数据量不是很大，为 1 <= maxLetters <= 26，我们试一下暴力法。
## 公司
* 字节
### 思路
暴力法如下：
* 先找出所有满足长度大于等于 minSize 且小于等于 maxSize 的所有子串。（平方的复杂度）
* 对于 maxLetter 满足题意的子串，我们统计其出现次数。时间复杂度为 O(k),其中 k 为子串长度
* 返回最大的出现次数
### 代码
Pythpn Code:
```python
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n = len(s)
letters = set()
cnts = dict()
res = 0
for i in range(n - minSize + 1):
length = minSize
while i + length <= n and length <= maxSize:
t = s[i:i + length]
for c in t:
if len(letters) > maxLetters:
break
letters.add(c)
if len(letters) <= maxLetters:
cnts[t] = cnts.get(t, 0) + 1
res = max(res, cnts[t])
letters.clear()
length += 1
return res
```
上述代码会超时。我们来利用剪枝来优化。
## 剪枝
### 思路
还是暴力法的思路，不过我们在此基础上进行一些优化。首先我们需要仔细阅读题目，如果你足够细心或者足够有经验，可能会发现其实题目中 maxSize 没有任何用处，属于干扰信息。
也就是说我们没有必要统计`长度大于等于 minSize 且小于等于 maxSize 的所有子串`，而是统计长度为 minSize 的所有字串即可。原因是，如果一个大于 minSize 长度的字串若是满足条件，那么该子串其中必定有至少一个长度为 minSize 的字串满足条件。因此一个大于 minSize 长度的字串出现了 n 次，那么该子串其中必定有一个长度为 minSize 的子串出现了 n 次。 **也就是说对于给定起点的子串，大于 minSize 的子串一定不会比 minSize 的子串更优**。
### 代码
代码支持 Python3，Java：
Python Code：
```python
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
counter, res = {}, 0
for i in range(0, len(s) - minSize + 1):
sub = s[i : i + minSize]
if len(set(sub)) <= maxLetters:
counter[sub] = counter.get(sub, 0) + 1
res = max(res, counter[sub])
return res;
# @lc code=end
```
Java Code：
```java
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map counter = new HashMap<>();
int res = 0;
for (int i = 0; i < s.length() - minSize + 1; i++) {
String substr = s.substring(i, i + minSize);
if (checkNum(substr, maxLetters)) {
int newVal = counter.getOrDefault(substr, 0) + 1;
counter.put(substr, newVal);
res = Math.max(res, newVal);
}
}
return res;
}
public boolean checkNum(String substr, int maxLetters) {
Set set = new HashSet<>();
for (int i = 0; i < substr.length(); i++)
set.add(substr.charAt(i));
return set.size() <= maxLetters;
}
```
**复杂度分析**
其中 N 为 s 长度
* 时间复杂度：$O(N \* minSize)$
* 空间复杂度：$O(N \* minSize)$
## 关键点解析
* 滑动窗口
* 识别题目干扰信息
* 看题目限制条件，对于本题有用的信息是`1 <= maxLetters <= 26`
## 扩展
我们也可以使用滑动窗口来解决，感兴趣的可以试试看。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1297.maximum-number-of-occurrences-of-a-substring.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.