给你一个字符串 s ,请你返回满足以下条件且出现次数最大的 任意 子串的出现次数:
示例 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^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s 只包含小写英文字母。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-number-of-occurrences-of-a-substring 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map<string, int> m;
int i, j, c, count, maxcount = 0, n = s.size();
string t;
for(i = 0; i <= n-minSize; ++i)
{
t = s.substr(i, minSize);//子串
count = 0, c = 0;
for(j = 0; j < t.size(); ++j)
{
if(((count>>(t[j]-'a'))&1)==0)//没有出现的字符
{
c++;//种数+1
count |= (1<<(t[j]-'a'));//该位置为1
}
}
if(c <= maxLetters)//字符种数满足要求
{
m[t]++;//计数+1
maxcount = max(maxcount,m[t]);//更新最大计数
}
}
return maxcount;
}
};
144 ms 14 MB