Leetcode.1297 子串的最大出现次数

题目链接

Leetcode.1297 子串的最大出现次数 Rating ： 1748

题目描述

给你一个字符串 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只包含小写英文字母。

解法：滑动窗口

一个显而易见的结论：给定一个字符串 s，t是 s中的一个子串，且 s在 t中出现了 k次。那么 t的任何一个子串在 s中也至少出现了 k次。

所以对于题目给定的 minSize和 masSize，我们就只需要考虑 minSize。

每次截取长度为 minSize的子串，查看是否符合条件。记录其中最大的出现次数。

时间复杂度：$O(n\ast minSize)$

C++代码：

class Solution {
public:
    int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
        int n = s.size();
        unordered_map<string,int> cnt;
        int ans = 0;

        for(int i = 0;i < n - minSize + 1;i++){
            string ss = s.substr(i,minSize);
            unordered_set<char> uset(ss.begin(),ss.end());
            if(uset.size() <= maxLetters){
                cnt[ss]++;
                ans = max(ans,cnt[ss]);
            }
        }

        return ans;
    }
};