不容易解的题10.15

395.至少有K个重复字符的最长字串

395. 至少有 K 个重复字符的最长子串 - 力扣（LeetCode）https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/?envType=list&envId=ZCa7r67M自认为是不好做的题。尤其是使用滑动窗口解法，思路很难想

一开始的想法很简单，思路也是该ac的思路，但是测试用例太长，超时了

思路是取该字符串上的每一个子串，这里的实现是用双for确定子串的开始和结束位置，将该字串传递进一个自写函数，该函数作用是用一个数组做哈希表来判断每个字符是否出现了k次及以上，如果是返回true，并且判断当前子串长度是否是被记录最长，如果不是更新答案，遍历完之后返回正确的长度即可。

class Solution {
public:int longestSubstring(string s, int k) {int res=0;for(int i=0;i<s.size();i++){for(int j=i;j<s.size();j++){if(fun(s,i,j,k)&&res<j-i+1)res=j-i+1;}}return res;}bool fun(string &s,int left,int right,int k){int arr[26]={0};for(int i=left;i<=right;i++)arr[s[i]-'a']++;for(int i=0;i<26;i++){if(arr[i]!=0&&arr[i]<k)return false;}return true;}
};

做的时候一直以为该思路是可以通过的，然后做了很多次剪枝，发现通不过去。

下面来看正确的滑动窗口实现，是我看一个网友写的，思路十分清晰易懂，后来发现官方题解的滑窗也是这样的思路，但是官方题解一般很难看得懂。

class Solution {
public:int longestSubstring(string s, int k) {int res=0;int arr[26]={0};for(int i=1;i<=26;i++){int left=0,right=0;int diff=0,count=0;memset(arr,0,sizeof(arr));while(right<s.size()){arr[s[right]-'a']++;if(arr[s[right]-'a']==1)diff++;if(arr[s[right]-'a']==k)count++;right++;while(left<right&&diff>i){arr[s[left]-'a']--;if(arr[s[left]-'a']==0)diff--;if(arr[s[left]-'a']==k-1)count--;left++;}if(diff==i&&diff==count)res=max(res,right-left);}}return res;}
};

我们先给出代码，以代码来分析。

循环是以26个不同的字母为限制的，即每次只允许窗口内存在n个不同的字母
设置变量来分别存放当前窗口内不同种类字符的个数、符合该种字符个数等于k的字符有多少个、窗口左边界、窗口右边界
变量设置好后，开始进入第一个while，它是扩张右窗口的
如果当前数组位置为1，diff++，说明有不同的字符第一次加进来
如果当前位置数值为k则count++说明当前字符出现次数第一次达到k，注意这里并不是大于等于k时候count++，这样的话后续加进来该字符会导致重复计数
如果当前窗口出现的字符种类大于i，进入左边界缩小的阶段，进入的是循环而不是if判断语句
循环中如果左边界在右边界左侧，说明该窗口有缩减的必要，并且还要保证此时窗口字符种类大于i
进入之后是和上面类似的判断，不停增大left直到字符种类在允许的范围内
值得注意的有两点：
第一：判断窗口种类个数是否超过i的循环，应该在扩大右边界循环内部，每扩大一次右边界，并完成相应变量增加后，就立即判断此时左边界是否应该缩小
第二：判断完左右边界之后，立即进行的是一句判断
如果当前所允许的字符种类个数等于当前窗口的字符种类个数，并且窗口里任意字符的个数都大于或等于k，则判断是否应该更新答案值
为什么要判断现在最大允许的字符种类个数呢？
因为该循环是由1开始到26结束，每次判断的是最大允许范围这能保证当前窗口前提下，找到的是最大的数值，这样才可能需要更新数据
一定要注意不要把更新数据这条语句不小心写到循环外面了，这样如果在窗口移动时有新数据，就添加不上了

memset每次清理数组很重要，上一次遗留的数据不能作为下一次扩大i限制的哈希表，这会造成不同字母为1时和字母为2时的哈希表累加，这在逻辑上也说不过去
right++可以放在最后，这样使代码更容易理解，当然代码也应该写成right-left+1
注意vector数组的clear不能起到相同的作用
还有就是不要把-‘a’写成-‘0’

还有一种方法是递归：

这种方法，十分巧妙，但是更难想，我一般倾向于能不用递归就不用递归，递归一般思路不好想，而且出bug也不太容易找。

也是先给出代码再看思路

class Solution {
public:int longestSubstring(string s, int k) {unordered_set<char> set(s.begin(),s.end());unordered_map<char,int>map;for(char ch:s)map[ch]++;for(char ch:set){vector<string>path;if(map[ch]<k){split(s,path,ch);int res=0;for(string tn:path){res=max(longestSubstring(tn,k),res);}return res;}}return s.size();}void split(const string&s,vector<string>&path,const char flag=' '){path.clear();istringstream iss(s);string temp;while(getline(iss,temp,flag)){path.push_back(temp);}
}
};

大概的理解：
map记录的是s字符串中每个出现过的字符都有多少个，如果全都大于k那么进不到if循环，直接返回s.size（）了，因为整个字符串就符合题解
如果有小于k的说明只要包含该字符的子串都不能满足条件，因为map存储的是s这个字符串中该字符出现的总次数，如果小于那么进行分割，分割出不含该字符的若干字串，将这些子串全部放入一个数组里，然后进行递归，找这些子串中最长的满足条件的长度是多少
如果此时分割出来的子串中含有小于k次频率的字符怎么办？
不用担心，res=max这一行，会再次进入函数，进行分割，直到子串全部满足大于等于k的出现频率
不必深究代码究竟如何进行递归，我们只需要搞清楚分割的条件，以及答案将返回什么即可

怎么样是不是理解起来比滑窗稍难一些，也可能是我个人使用递归很少，所以感觉很难想，用哈希表存每个字符出现频次，然后再把不满足频次的字符分割开，这种思路很巧妙。

---

都看到这里了如果对您有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注