第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
1297. 子串的最大出现次数

题目描述

1
给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:
2
3
子串中不同字母的数目必须小于等于 maxLetters 。
4
子串的长度必须大于等于 minSize 且小于等于 maxSize 。
5
6
7
示例 1:
8
9
输入:s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
10
输出:2
11
解释:子串 "aab" 在原字符串中出现了 2 次。
12
它满足所有的要求:2 个不同的字母,长度为 3 (在 minSize 和 maxSize 范围内)。
13
示例 2:
14
15
输入:s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
16
输出:2
17
解释:子串 "aaa" 在原字符串中出现了 2 次,且它们有重叠部分。
18
示例 3:
19
20
输入:s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
21
输出:3
22
示例 4:
23
24
输入:s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
25
输出:0
26
27
28
提示:
29
30
1 <= s.length <= 10^5
31
1 <= maxLetters <= 26
32
1 <= minSize <= maxSize <= min(26, s.length)
33
s 只包含小写英文字母。
Copied!

前置知识

  • 字符串
  • 滑动窗口

暴力法

题目给的数据量不是很大,为 1 <= maxLetters <= 26,我们试一下暴力法。

公司

  • 字节

思路

暴力法如下:
  • 先找出所有满足长度大于等于 minSize 且小于等于 maxSize 的所有子串。(平方的复杂度)
  • 对于 maxLetter 满足题意的子串,我们统计其出现次数。时间复杂度为 O(k),其中 k 为子串长度
  • 返回最大的出现次数

代码

Pythpn Code:
1
class Solution:
2
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
3
n = len(s)
4
letters = set()
5
cnts = dict()
6
res = 0
7
for i in range(n - minSize + 1):
8
length = minSize
9
while i + length <= n and length <= maxSize:
10
t = s[i:i + length]
11
for c in t:
12
if len(letters) > maxLetters:
13
break
14
letters.add(c)
15
if len(letters) <= maxLetters:
16
cnts[t] = cnts.get(t, 0) + 1
17
res = max(res, cnts[t])
18
letters.clear()
19
length += 1
20
return res
Copied!
上述代码会超时。我们来利用剪枝来优化。

剪枝

思路

还是暴力法的思路,不过我们在此基础上进行一些优化。首先我们需要仔细阅读题目,如果你足够细心或者足够有经验,可能会发现其实题目中 maxSize 没有任何用处,属于干扰信息。
也就是说我们没有必要统计长度大于等于 minSize 且小于等于 maxSize 的所有子串,而是统计长度为 minSize 的所有字串即可。原因是,如果一个大于 minSize 长度的字串若是满足条件,那么该子串其中必定有至少一个长度为 minSize 的字串满足条件。因此一个大于 minSize 长度的字串出现了 n 次,那么该子串其中必定有一个长度为 minSize 的子串出现了 n 次。 也就是说对于给定起点的子串,大于 minSize 的子串一定不会比 minSize 的子串更优

代码

代码支持 Python3,Java:
Python Code:
1
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
2
counter, res = {}, 0
3
for i in range(0, len(s) - minSize + 1):
4
sub = s[i : i + minSize]
5
if len(set(sub)) <= maxLetters:
6
counter[sub] = counter.get(sub, 0) + 1
7
res = max(res, counter[sub])
8
return res;
9
10
# @lc code=end
Copied!
Java Code:
1
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
2
Map<String, Integer> counter = new HashMap<>();
3
int res = 0;
4
for (int i = 0; i < s.length() - minSize + 1; i++) {
5
String substr = s.substring(i, i + minSize);
6
if (checkNum(substr, maxLetters)) {
7
int newVal = counter.getOrDefault(substr, 0) + 1;
8
counter.put(substr, newVal);
9
res = Math.max(res, newVal);
10
}
11
}
12
return res;
13
}
14
public boolean checkNum(String substr, int maxLetters) {
15
Set<Character> set = new HashSet<>();
16
for (int i = 0; i < substr.length(); i++)
17
set.add(substr.charAt(i));
18
return set.size() <= maxLetters;
19
}
Copied!
复杂度分析
其中 N 为 s 长度
  • 时间复杂度:$O(N * minSize)$
  • 空间复杂度:$O(N * minSize)$

关键点解析

  • 滑动窗口
  • 识别题目干扰信息
  • 看题目限制条件,对于本题有用的信息是1 <= maxLetters <= 26

扩展

我们也可以使用滑动窗口来解决,感兴趣的可以试试看。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。