1297. 子串的最大出现次数 · ttttt

# 1297. 子串的最大出现次数 # 题目地址（1297. 子串的最大出现次数） <https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring/> ## 题目描述 ``` <pre class="calibre18">``` 给你一个字符串 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 <= maxLetters <= 26，我们试一下暴力法。 ## 公司 - 字节 ### 思路暴力法如下： - 先找出所有满足长度大于等于 minSize 且小于等于 maxSize 的所有子串。（平方的复杂度） - 对于 maxLetter 满足题意的子串，我们统计其出现次数。时间复杂度为 O(k),其中 k 为子串长度 - 返回最大的出现次数 ### 代码 Pythpn Code: ``` <pre class="calibre18">``` class Solution: def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: n = len(s) letters = set() cnts = dict() res = 0 for i in range(n - minSize + 1): length = minSize while i + length <= n and length <= maxSize: t = s[i:i + length] for c in t: if len(letters) > maxLetters: break letters.add(c) if len(letters) <= maxLetters: cnts[t] = cnts.get(t, 0) + 1 res = max(res, cnts[t]) letters.clear() length += 1 return res ``` ``` 上述代码会超时。我们来利用剪枝来优化。 ## 剪枝 ### 思路还是暴力法的思路，不过我们在此基础上进行一些优化。首先我们需要仔细阅读题目，如果你足够细心或者足够有经验，可能会发现其实题目中 maxSize 没有任何用处，属于干扰信息。也就是说我们没有必要统计`长度大于等于 minSize 且小于等于 maxSize 的所有子串`，而是统计长度为 minSize 的所有字串即可。原因是，如果一个大于 minSize 长度的字串若是满足条件，那么该子串其中必定有至少一个长度为 minSize 的字串满足条件。因此一个大于 minSize 长度的字串出现了 n 次，那么该子串其中必定有一个长度为 minSize 的子串出现了 n 次。 ### 代码代码支持 Python3，Java： Python Code： ``` <pre class="calibre18">``` def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int: counter, res = {}, 0 for i in range(0, len(s) - minSize + 1): sub = s[i : i + minSize] if len(set(sub)) <= maxLetters: counter[sub] = counter.get(sub, 0) + 1 res = max(res, counter[sub]) return res; # @lc code=end ``` ``` Java Code： ``` <pre class="calibre18">``` public int maxFreq(String s, int maxLetters, int minSize, int maxSize) { Map<String, Integer> counter = new HashMap<>(); int res = 0; for (int i = 0; i < s.length() - minSize + 1; i++) { String substr = s.substring(i, i + minSize); if (checkNum(substr, maxLetters)) { int newVal = counter.getOrDefault(substr, 0) + 1; counter.put(substr, newVal); res = Math.max(res, newVal); } } return res; } public boolean checkNum(String substr, int maxLetters) { Set<Character> set = new HashSet<>(); for (int i = 0; i < substr.length(); i++) set.add(substr.charAt(i)); return set.size() <= maxLetters; } ``` ``` **复杂度分析** 其中 N 为 s 长度 - 时间复杂度：O(N∗minSize)O(N \* minSize)O(N∗minSize) - 空间复杂度：O(N∗minSize)O(N \* minSize)O(N∗minSize) ## 关键点解析 - 滑动窗口 - 识别题目干扰信息 - 看题目限制条件，对于本题有用的信息是`1 <= maxLetters <= 26` ## 扩展我们也可以使用滑动窗口来解决，感兴趣的可以试试看。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)