1297. 子串的最大出现次数

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/
Star
给你一个字符串 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 只包含小写英文字母。

法 1 滑动窗口

思路
有个脑筋急转弯！长的子串一定是覆盖短的子串的，所以只需要找最短的子串即可
题解
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        wds = defaultdict(int)
        res = defaultdict(int)

        l, r = 0, 0
        while r < len(s):
            cur_char = s[r]
            r += 1
            wds[cur_char] += 1

            while l < r and (len(wds) > maxLetters or r - l > minSize):
                delet_char = s[l]
                l += 1
                wds[delet_char] -= 1
                if wds[delet_char] == 0:
                    del wds[delet_char]

            if r-l == minSize:
                res[s[l:r]] += 1

        return max(res.values()) if len(res) > 0 else 0