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了。

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;
    }
};