LeetCode 1297. 子串的最大出现次数数据结构与算法Michael是个半路程序员-

1. 题目

给你一个字符串 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^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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 最大长度的字符串如果是答案，那么最小长度的肯定也是答案，所以只需要考虑最小长度
• 对字符串每个字符开始的最小长度个字符组成的子串，检查其字符种数是否满足

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