题目描述

给你一个字符串 s，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：

• 子串中不同字母的数目必须小于等于 maxLetters。
• 子串的长度必须大于等于 minSize 且小于等于 maxSize。

样例

输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

输入：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 只包含小写英文字母。

算法

(贪心，暴力枚举) $O(n \cdot minSize)$

1. 很显然我们只需要找长度等于 minSize 的符合条件的子串。因为对于任何一个长度大于 minSize 符合条件的子串，都可以从中构造出一个长度等于 minSize 且符合条件的子串。
2. 我们只需要枚举所有长度等于 minSize 的子串，将其放入哈希表中，然后找到一个出现次数最多，且满足不同字母要求的子串。

时间复杂度

• 共有 $O(n)$ 个子串，每个子串需要 $O(minSize)$ 的时间判断，故总时间复杂度为 $O(n \cdot minsize)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存放哈希表。

C++ 代码

class Solution {
public:
    int count(const string& s) {
        vector<bool> v(26, false);
        int tot = 0;

        for (char c : s)
            if (!v[c - 'a']) {
                tot++;
                v[c - 'a'] = true;
            }

        return tot;
    }

    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int n = s.length();
        int ans = 0;
        unordered_map<string, int> mp;
        for (int i = 0; i < n - minSize + 1; i++)
            mp[s.substr(i, minSize)]++;

        for (auto it = mp.begin(); it != mp.end(); it++)
            if (count(it -> first) <= maxLetters)
                ans = max(ans, it -> second);

        return ans;
    }
};