1297. Maximum Number of Occurrences of a Substring

sliding window O(minSize * n) time O(n) space
这道题的trick是如果maxSize的子串多次出现则minSize的子串只会出现更多次因为短子串一定包含在长子串里，所以只需要检查minSize子串即可！！

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int res = 0;
        unordered_map<string, int> f;
        unordered_map<char, int> m;
        for (int l = 0, r = 0; r < size(s); ++r) {
            ++m[s[r]];
            if (r >= minSize) {
                if (--m[s[l]] == 0) {
                    m.erase(s[l]);
                }
                ++l;
            }
            if (r >= minSize - 1 && size(m) <= maxLetters) {
                res = max(res, ++f[s.substr(l, minSize)]);
            }
        }
        return res;
    }
};

sliding window O((maxSize - minSize) * n * len) time O(n) space

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int res = 0;
        for (int n = size(s), len = minSize; len <= maxSize; ++len) {
            unordered_map<string, int> f;
            unordered_map<char, int> m;
            for (int l = 0, r = 0; r < n; ++r) {
                ++m[s[r]];
                if (r >= len) {
                    if (--m[s[l]] == 0) {
                        m.erase(s[l]);
                    }
                    ++l;
                }
                if (r >= len - 1 && size(m) <= maxLetters) {
                    res = max(res, ++f[s.substr(l, len)]);
                }
            }
        }
        return res;
    }
};