题目地址（1297. 子串的最大出现次数）
https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring
题目描述
给你一个字符串 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:
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：
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：
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; }
关键点解析
- 滑动窗口
- 识别题目干扰信息
- 看题目限制条件，对于本题有用的信息是
1 <= maxLetters <= 26
扩展
我们也可以使用滑动窗口来解决，感兴趣的可以试试看。
LeetCode题解1020.number-of-enclaves题目地址 https://leetcode-cn.com/problems/number-of-enclaves/ 题目描述 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。 示例 1： 输入…
LeetCode题解104.maximum-depth-of-binary-tree题目地址 https://leetcode.com/problems/maximum-depth-of-binary-tree/description/ 题目描述 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the lo…
LeetCode题解1131.maximum-of-absolute-value-expression题目地址（1131. 绝对值表达式的最大值） https://leetcode-cn.com/problems/maximum-of-absolute-value-expression/description/ 题目描述 给你两个长度相等的整数数组，返回下面表达式的最大值： |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| …
LeetCode题解1031.maximum-sum-of-two-non-overlapping-subarrays题目地址 https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/ 题目描述 Given an array A of non-negative integers, return the maximum sum of elements in two non-overl…
LeetCode题解1218.longest-arithmetic-subsequence-of-given-difference题目地址 https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/ 题目描述 给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序…