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

题目链接
思路：分治+逻辑分割
分析：要求连续的字符串最长，并且组成字符串的每个字符出现的次数都不能小于k，那么我们可以反过来想。
也就是说：字符串中的出现次数小于k的，肯定不会是答案。并且答案一定不会包含这个字符在内。
那么我们统计一下字符串中每个字符出现的次数。
然后找到出现出现次数少于k的，然后按照这个字符去切割这个字符串。
代码：

class Solution {    //每次把在[left, right]中字符出现次数少于k的找出来，然后按照这个将字符串切割开，因为不可能包含这个字符    //然后从字串中，继续寻找是否存在范围内字符次数少于k的，如果没有，那么长度就是整个，否则，继续按照这个不可能的字符继续切割    public int longestSubstring(String s, int k) { return dfs(s, 0, s.length()-1, k);    }    public int dfs(String s, int left, int right, int k){ int[] words = new int[26]; //统计在范围内的字符出现的次数 for(int i=left; i<=right; i++){     words[s.charAt(i)-'a']++; } //记录这个不可能的字符 char split = 0; for(int i=0; i<26; i++){     if(words[i]>0 && words[i]<k){  //这个字符出现的次数大于0小于k，就是不可能的字符  split = (char)(i+'a');  break;     } } //如果没有不可能的字符，那么答案就是整个字符串的长度 if(split==0){     return right - left+1; } //记录当前答案 int res = 0; //工作指针 int i = left; while(i <= right){     //寻找新的左边，如果左边一开始就是不可能字符，那么就切除     while(i<=right && s.charAt(i)==split){  i++;     }     //如果i是>right出来的上面的循环，那么说明全都是不可能字符，直接退出循环     if(i>right){  break;     }     //start就是新的左边     int start = i;     //寻找新的右边     while(i<=right && s.charAt(i)!=split){  i++;     }     //寻找下一轮范围内的答案     int len = dfs(s, start, i-1, k);     //和当前答案取最大     res = Math.max(res, len); } return res;    }}