题目一：至少有 K 个重复字符的最长子串 395. 至少有 K 个重复字符的最长子串 题目解析 有两种方法：递归分治解决：该分治法的应用对象：解决那种不会去跨越任何一个段更新答案的题目。比如此题这种关于字符串子串的题。首先在整个字符串大范围内可以确定哪些字符没有达到k次，故只要存在这些字符的子串都被排除在外。具体到递归分治的代码上就是： 分治的每一段都不含上一个总字符串的被 ban (被禁)字符，故每个分治的对象都要进行以下几个步骤： 一、计算 [l,r] 之间所有字符的出现次数。 二、根据出现次数计算出被 ban 掉的字符类型。 三、根据是否有被 ban 的字符类型，来确定是否还需要再往下递归分治，如果没有被 ban 的字符类型，则该字符串就是一个符合条件的字符串。否则继续往下递归分治，分治的子对象都不能含有该被 ban 字符类型。根据枚举类型的滑动窗口解决：按照字符类型的滑动窗口技巧，最外层用于枚举固定当前窗口内最多有多少类型。这个技巧就是，当我们无法直接找到滑动窗口的边界时，我们可以根据有限的类型来构造滑动窗口的边界，由于最多有26个类型的字符，而我们滑动窗口过程可以根据某个类型的字符数量是否符合条件来得到窗口内符合条件的类型数量，只要窗口内的类型数量等于符合条件的类型数量，那么该窗口内的字符串即为一个答案。但问题是，我们不清楚窗口内的类型数量是多大，这也就是我们没有明确的边界，此时我们根据枚举 1~26 个类型来进行窗口的滑动限制即可。解题代码法一：递归分治class Solution { public: int dfs(string& s,int l,int r,int k){ int cnt[26] = {0}; for(int i=l;i<=r;i++){//计算字符的次数方便计算ban掉的字符类型 cnt[s[i]-'a']++; } char split = 0; for(int i=0;i<26;i++){ if(cnt[i]!=0&&cnt[i]<k){ //很明显在这个大范围内要是这个字符类型次数都小于k了，肯定就是要被ban的 split = i+'a'; break; } } if(split==0)//如果该段字符串没有被ban的字符类型则该字符串就是符合条件的字符串 return r-l+1; int ret = 0; //开始枚举分治到下面去 while(l<=r){ while(l<=r&&s[l]==split){//不让起始点从被ban的字符开始 l++; } if(l>r) break;//说明全是被ban的字符 int start = l; while(l<=r&&s[l]!=split){//计算本次分段的长度（结束位置） l++; } int length = dfs(s,start,l-1,k); ret = max(ret,length); } return ret; } int longestSubstring(string s, int k) { return dfs(s,0,s.size()-1,k); } }; 法二：枚举类型的滑动窗口class Solution { public: int longestSubstring(string s, int k) { int n = s.size(); int cnt[26]{0};//用于记录窗口内字符的出现次数 int maxLen = 0; for(int i=1;i<=26;i++){ memset(cnt,0,sizeof(cnt)); for(int l=0,r=0,sum=0,tot=0;r<n;r++){//sum、tot分别表示窗口内的有效字符种类数和总的种类数 cnt[s[r]-'a']++; if(cnt[s[r]-'a']==1) //增加种类数 tot++; if(cnt[s[r]-'a']==k) //为了防止多次更新千万别取大于号 sum++; //增加有效种类数 while(tot>i){ //达到收缩窗口条件，因为窗口内的种类数限制为i个 int dup = (s[l++]-'a'); cnt[dup]--; if(cnt[dup]==0) //种类数此时需要-1 tot--; if(cnt[dup]==k-1)//有效种类数-1 sum--; } if(sum==tot) maxLen = max(maxLen,r-l+1); } } return maxLen; } }; 题目二：最长的美好子字符串 最长的美好子字符串 题目解析 这题虽然由于数据量的关系，被划分为简单题，但实际上完全不亚于第一题。甚至还得用上一些位运算的思想。 这题我会的做法只有两种：普通位运算枚举法：其实就是此题的暴…