对于 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
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;
}
