LeetCode 1297 子串的最大出现次数
🟠 中等偏上
https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/description/
特殊的点
如果字符串 abcf 出现了5次，那么 abc 一定不止出现了5次。也就是说：短的字符串出现的次数一定比长的出现次数多。
因此可以用最短的限制长度 minSize 来滑动收集每种子串出现的次数，另外还要限制窗口内的字母种类数目因此窗口用 hash_map 维护，每种子串也用 hash_map 维护。
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map<char,int> char_count;
unordered_map<string,int> sub_str;
for(int i = 0;i<=minSize-2;i++){
char_count[s[i]]++;
}
int max_count = 0;
for(int i = minSize-1;i<s.size();i++){
char_count[s[i]]++;
if(char_count.size()<=maxLetters){
sub_str[s.substr(i-minSize+1,minSize)]++;
max_count = max(max_count,sub_str[s.substr(i-minSize+1,minSize)]);
}
char_count[s[i-minSize+1]]--;
if(char_count[s[i-minSize+1]]==0){
char_count.erase(s[i-minSize+1]);
}
}
return max_count;
}
};