题目描述
给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
- 子串中不同字母的数目必须小于等于 maxLetters 。
- 子串的长度必须大于等于 minSize 且小于等于 maxSize
思路
一.滑窗+穷举+去重
根据第一个条件：子串中不同字母的数量必须
<= maxLetters
，可以想到用滑窗。那么我们用一个滑窗，从左到右扫描这个字符串，只要遇到窗口内的不同字母数
<= maxLetters
，就停下来，扫描窗口内的全部长度介于
[minSize, maxSize]
的子串（穷举所有长度满足条件的子串），加入到一个用于计数的
Map
中，并实时更新答案即可。注意，滑动窗口移动的过程中，窗口内的子串可能会被重复添加，所以需要去重，去重的标准是子串的起始位置
[l,r]
。只有当某组
[l,r]
没有被添加过时，才添加该子串。
/**
* 553ms 14%
* 223MB
**/
class Solution {
int BASE = 1_000_00;
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
// HashTable + SlideWindow
Map<String, Integer> freqMap = new HashMap<>();
Set<Long> st = new HashSet<>(); // 用来去重
int ans = 0;
int[] cnt = new int[26]; // 计数
int kind = 0; // 字母种类个数
char[] cs = s.toCharArray();
for (int i = 0, j = 0; i < cs.length; i++) {
int u = cs[i] - 'a';
cnt[u]++;
if (cnt[u] == 1) kind++;
// 先收缩窗口的左边界, 将字符种类数满足条件
while (kind > maxLetters) {
u = cs[j] - 'a';
cnt[u]--;
if (cnt[u] == 0) kind--;
j++;
}
// 在[j, i]区间内, 寻找全部长度满足[minSize, maxSize]的子串
for (int begin = j; begin + minSize - 1 <= i; begin++) {
for (int end = begin + minSize - 1; end <= i; end++) {
long hash = begin * BASE + end; // 将区间[begin, end] 进行序列化并保存
// 这个区间的子串已经被扫描过, 跳过
if (st.contains(hash)) continue;
st.add(hash);
String sub = s.substring(begin, end + 1);
freqMap.put(sub, freqMap.getOrDefault(sub, 0) + 1);
ans = Math.max(ans, freqMap.get(sub));
}
}
}
return ans;
}
}
由于每次找到一个字母种类数满足条件的区间，就会对区间内进行全部扫描，会有很多区间被重复扫描过，效率比较低。
O
(
n
2
×
S
2
)
O(n^2 \times S^2 )
O
(
n
2
×
S
2
)
，外层滑窗的循环，复杂度为
O
(
n
)
O(n)
O
(
n
)
，每找到一个区间后，扫描全部子串的复杂度为
O
(
n
×
S
2
)
O(n \times S^2)
O
(
n
×
S
2
)
其中
n
n
n
表示字符串长度，
S
S
S
表示
minSize
和
maxSize
的数量级，在本题中是
26
。
二.滑窗+固定求解长度为minSize的子串
看了题解后，发现可以进行优化。假设满足条件，且出现次数最多的子串为
T
，那么
T
的子串中，若有满足条件的，出现次数与
T
相同，但长度比
T
短。也就是说，只要能找到一个
T
，是出现次数最多的子串，那么一定能找到
T
的某个子串，出现次数也一样多。而
T
的子串中，要满足条件，其长度一定要满足
maxSize >= len >= minSize
，所以我们可以只取长度为
minSize
的子串进行求解即可。
同样借助滑窗，代码优化如下：
/**
* 27ms 86%
* 43.5MB
**/
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int ans = 0, n = s.length();
char[] cs = s.toCharArray();
int[] cnt = new int[26];
Map<String, Integer> map = new HashMap<>();
int kind = 0;
for (int i = 0, j = 0; i < n; i++) {
int u = cs[i] - 'a';
cnt[u]++;
if (cnt[u] == 1) kind++;
// 先让字母种类数满足条件, 然后让长度减小到minSize
while (kind > maxLetters || i - j + 1 > minSize) {
u = cs[j] - 'a';
cnt[u]--;
if (cnt[u] == 0) kind--;
j++;
}
// 若长度为minSize, 则记录答案
if (i - j + 1 == minSize) {
String sub = s.substring(j, i + 1);
map.put(sub, map.getOrDefault(sub, 0) + 1);
ans = Math.max(ans, map.get(sub));
}
}
return ans;
}
}
若
substring
截取子串的复杂度为
O
(
1
)
O(1)
O
(
1
)
的话，总的时间复杂度
O
(
n
)
O(n)
O
(
n
)
，因为只需要一次滑窗。上面
的思路，可以这样理解，相当于尝试找到以每个位置作为结尾，且满足条件（字母种类
<=maxLetters
以及长度为
minSize
）的子串。
三.枚举全部长度为minSize的子串
由于只需要找长度为
minSize
的子串，一个简单的想法就是，枚举全部长度为
minSize
的子串，并用一个
Set
来统计其中的字符种类。
/**
* 53ms 41%
* 44MB
**/
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<String, Integer> map = new HashMap<>();
Set<Character> set = new HashSet<>();
int n = s.length();
char[] cs = s.toCharArray();
int ans = 0;
for (int i = 0; i + minSize - 1 < n; i++) {
int end = i + minSize - 1;
for (int j = i; j <= end; j++) set.add(cs[j]);
if (set.size() <= maxLetters) {
String ss = s.substring(i, end + 1);
map.put(ss, map.getOrDefault(ss, 0) + 1);
ans = Math.max(ans, map.get(ss));
}
set.clear();
}
return ans;
}
}
时间复杂度
O
(
n
×
S
)
O(n \times S)
O
(
n
×
S
)
，遍历全部子串需要
O
(
n
)
O(n)
O
(
n
)
，统计每个子串的字符数量需要
O
(
S
)
O(S)
O
(
S
)
四.滑窗+字符串哈希
假设
substring
的时间复杂度不为
O
(
1
)
O(1)
O
(
1
)
，那么我们可以采用字符串哈希的方式，在
O
(
1
)
O(1)
O
(
1
)
的复杂度下求得一个子串（的唯一表示）
/**
* 25ms 92%
* 44MB
**/
class Solution {
long P = 131L;
long[] hash;
long[] p;
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
Map<Long, Integer> map = new HashMap<>();
// 字符串哈希
int n = s.length();
hash = new long[n + 1];
p = new long[n + 1];
p[0] = 1;
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
hash[i + 1] = hash[i] * P + c; // 溢出即取模
p[i + 1] = p[i] * P;
}
int[] cnt = new int[26];
int kind = 0, ans = 0;
for (int i = 0, j = 0; i < n; i++) {
char c = s.charAt(i);
int u = c - 'a';
cnt[u]++;
if (cnt[u] == 1) kind++;
while (kind > maxLetters || i - j + 1 > minSize) {
c = s.charAt(j);
u = c - 'a';
cnt[u]--;
if (cnt[u] == 0) kind--;
j++;
}
if (i - j + 1 == minSize) {
// 计算 [j, i] 之间的字符串哈希
// 对应的区间为 [j + 1, i + 1]
long t = hash[i + 1] - hash[j] * p[minSize];
map.put(t, map.getOrDefault(t, 0) + 1);
ans = Math.max(ans, map.get(t));
}
}
return ans;
}
}
时间复杂度为
O
(
n
)
O(n)
O
(
n
)
，预处理
O
(
n
)
O(n)
O
(
n
)
，滑窗
O
(
n
)
O(n)
O
(
n
)