class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
}
};
1297. 子串的最大出现次数
给你一个字符串 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^51 <= maxLetters <= 261 <= minSize <= maxSize <= min(26, s.length)s 只包含小写英文字母。原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.2 MB, 提交时间: 2023-06-01 10:22:16
func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
occurrences := make(map[string]int) //存储每个子串出现的次数
n := len(s)
for i := 0; i < n-minSize+1; i++ {
subs := s[i : i+minSize] //
if maxTypeNumber(subs) <= maxLetters {
occurrences[subs]++ //增加子串出现次数
}
}
m := 0
for _, v := range occurrences {
m = max(m, v)
}
return m
}
//MaxTypeNumber 取得字符串字符种类数量
func maxTypeNumber(s string) int {
mask := uint(0)
for _, ch := range s {
mask |= 1 << (unicode.ToLower(ch) - 'a')
}
return bits.OnesCount(mask)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 136 ms, 内存消耗: 18 MB, 提交时间: 2023-06-01 10:21:13
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
n=len(s)
d=collections.defaultdict(int)
for i in range(n-minSize+1):
temp=s[i:i+minSize]
c=set(temp)
if len(c)<=maxLetters:
d[temp]+=1
return max(d.values()) if d else 0
python3 解法, 执行用时: 160 ms, 内存消耗: 18.2 MB, 提交时间: 2023-06-01 10:20:33
class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
#给出一个窗口，窗口的范围是min和max
#窗口满足要求字母重复次数小于等于maxletters
cnt = Counter()
n = len(s)
for i in range(0,n-minSize+1):
#如果子串重复出现，该子串内的子串必然重复出现，故统计子串内最小即可
j = i + minSize
cnt[s[i:j]] += 1
for j in cnt.keys():
if len(set(j)) > maxLetters:
cnt[j] = 0
return max(cnt.values())
java 解法, 执行用时: 28 ms, 内存消耗: 43.8 MB, 提交时间: 2023-06-01 10:20:07
class Solution {
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
int n = s.length();
//统计子串出现的个数
Map<String,Integer> map = new HashMap<>();
char[] c = s.toCharArray();
int left = 0,right = 0;
//统计窗口中不同字母的数目
int tmp = 0;
//记录窗口中字母的个数
int[] count = new int[128];
while(right < n){
count[c[right]]++;
//当下面条件成立时，则说明窗口中多了一个不同的字母
if(count[c[right]] == 1) tmp++;
right++;
int len = right - left;
while(tmp > maxLetters || len > minSize){
count[c[left]]--;
//当窗口左移的过程中，一个字母减为0，则说明窗口中少了一个不同的字母
if(count[c[left]] == 0) tmp--;
left++;
//如果没有这句，会陷入死循环，len会一直大于minSize
len--;
}
//当不同字母的数目小于等于maxLetters
if(tmp <= maxLetters){
if(len == minSize){
String str = s.substring(left,right);
map.put(str,map.getOrDefault(str,0)+1);
}
}
}
//统计字串最大出现的次数
int ans = 0;
for(String key : map.keySet()){
ans = Math.max(ans,map.get(key));
}
return ans;
}
}