> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/sliding-window/static-size/1297.-maximum-number-of-occurrences-of-a-substring.md).

# 1297. Maximum Number of Occurrences of a Substring

Given a string `s`, return the maximum number of ocurrences of **any** substring under the following rules:

* The number of unique characters in the substring must be less than or equal to `maxLetters`.
* The substring size must be between `minSize` and `maxSize` inclusive.

**Example 1:**

```
Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
Output: 2
Explanation: Substring "aab" has 2 ocurrences in the original string.
It satisfies the conditions, 2 unique letters and size 3 (between minSize and maxSize).
```

**Example 2:**

```
Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
Output: 2
Explanation: Substring "aaa" occur 2 times in the string. It can overlap.
```

**Example 3:**

```
Input: s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
Output: 3
```

**Example 4:**

```
Input: s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
Output: 0
```

**Constraints:**

* `1 <= s.length <= 10^5`
* `1 <= maxLetters <= 26`
* `1 <= minSize <= maxSize <= min(26, s.length)`
* `s` only contains lowercase English letters.

字符串中出现次数最多且满足长度在\[minSize, maxSize]，独特的字符数不超过maxLetters的子符串出现的次数。遍历各个size，对每个size用滑动窗口和freq map统计满足条件的子字符串出现个数。注意到解出现在size > minSize时，它内部满足条件（独特字符数\<maxLetters）的子串一定也会出现在minSize的结果里，所以只需要遍历minSize就可以了。但如果条件换成独特字符数不小于minLetters，那就不能只遍历一个size了。

```cpp
class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        const int N = s.length();
        int res = 0;
        unordered_map<string, int> freqs;
        unordered_map<char, int> cnt;
        for (int i = 0; i < minSize; ++i) ++cnt[s[i]];
        if (cnt.size() <= maxLetters) ++freqs[s.substr(0, minSize)];
        for (int l = 0, r = minSize; r < N; ++l, ++r) {
            ++cnt[s[r]];
            --cnt[s[l]];
            if (cnt[s[l]] == 0) cnt.erase(s[l]);
            if (cnt.size() <= maxLetters) {
                auto sub = s.substr(l + 1, minSize);
                ++freqs[sub];
                res = max(res, freqs[sub]);
            }
        }
        return res;
    }
};
```