05 August 2008
给一个字符串 s ，返回满足以下条件且出现次数最大的 任意 子串的出现次数：
1
2
3
子串中不同字母的数目必须小于等于给定的maxLetters 。
子串的长度必须大于等于给定的minSize 且小于等于给定的maxSize 。
首先，题目的maxSizemaxSize是没有用的，因为maxSizemaxSize能够达到题目的最优解，minSizeminSize一定也能达到，因此只要考虑minSizeminSize即可。为什么这么说呢，我们举个例子，假设s = “aababcaab”，minSize = 2，maxSize = 3s=”aababcaab”，minSize=2，maxSize=3，那么我们通过maxSizemaxSize算出的解是”aab”“aab”,出现两次，那么”aab”“aab”的子串”aa”“aa”一定也出现至少有两次（可能会超过两次）。
然后，就是比较关键的minSizeminSize的大小 1 <= minSize <= maxSize <= min(26, s.length)1<=minSize<=maxSize<=min(26,s.length)。我们可以发现，这个minSizeminSize最大就是26。所以也就可以使用下面暴力算法了。
题目中还有一个条件是 子串中不同字母的数目必须小于等于 maxLetters子串中不同字母的数目必须小于等于maxLetters 。 然后我们用一个Map来统计满足这个条件的所有minSizeminSize大小的子串出现的次数，都统计完之后后面计算出现次数最多的就是答案。
用HashMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
private boolean isMatch(String str, int maxLetters) {
Set<Character> set = new HashSet<>();
for (char c : str.toCharArray()) {
set.add(c);
if (set.size() > maxLetters) {
return false;
}
}
return set.size() <= maxLetters;
}
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int len = s.length();
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < len; i++) {
if (i + minSize > len) {
break;
}
String sub = s.substring(i, i + minSize);
if (isMatch(sub, maxLetters)) {
map.put(sub, map.getOrDefault(sub, 0) + 1);
}
}
int result = 0;
for (String str : map.keySet()) {
int count = map.get(str);
if (count > result) {
result = count;
}
}
return result;
}
}