题目大意：
至少有K个重复字符的最长子串
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
示例 1:
输入: s = "aaabb", k = 3 输出: 3 最长子串为 "aaa" ，其中 'a' 重复了 3 次。
示例 2:
输入: s = "ababbc", k = 2 输出: 5 最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=395
解题思路分析：
本题暴力解的思路很好理解，两层循环，遍历每一个子串，查看其包含每种字符的个数是否都大于等于k就可以。遍历完所有子串，找一个最长的符合条件的长度返回即可。暴力解的时间复杂度为n的平方，如果字符串很长，不加剪枝的话大概率会TLE超时，因此我们需要思考更加效率的解题方式。
试想，符合条件的返回结果最多会包含26种小写字母，最少会包含1种字母。因此我们可以从1到26遍历每一种情况，即找出子串中包含n种字符的情况下的合理最长子串。遍历每一种情况时，我们需要定义如下几个变量：
- 数组count[]，统计当前子串中每种字符出现的次数
- type，当前子串中出现字符的种类数
- kCount，当前子串中，字符出现了k次或k次以上的种类数
接下来，使用双指针方式遍历字符串，起始时，2个指针left和right的位置均为0。先移动右指针，查看右指针指向的字符在区间内出现的次数，如果为0，说明该字符首次出现，为字符种类 type 加一。同时更新该字符在当前区间内出现的次数（加一）。如果该字符出现的次数等于k，说明该字符出现次数满足题目条件，为kCount 加一。此时，如果 type 等于 kCount，说明区间内出现的所有种类的字符个数都大于等于k，即当前区间为一个合理区间，利用当前区间长度更新全局最大值。
当前的操作是找出子串中包含n种字符的情况下的合理最长子串，因此当区间内字符种类数type小于等于当前n时，重复上述操作，向右移动右指针即可。当 type 大于n时，我们需要开始移动左指针来试图减少区间内字符种类，左指针划过的位置代表该字符将被移除出区间，首先查看左指针指向的字符在区间内出现的次数，如果次数等于k，说明左指针划过后，该字符个数将小于k，此时 kCount 减一，同时更新该字符在区间内的个数（减一）。更新后，如果该字符数等于0，说明该字符在区间内已经不存在，此时字符种类 type 减一。当type不再大于n时，结束移动左指针，返回继续移动右指针。
本解法的时间复杂度为n*26。
实现代码：
public int longestSubstring(String s, int k) {
// 为了使用方便，将字符串转为数组
char[] arr = s.toCharArray();
// 返回结果
int res=0;
// 从1到26，循环即找出子串中包含i种字符的情况下的合理最长子串
for(int i=1;i<=26;i++){
// 统计区间内每种字符出现次数
int[] count = new int[26];
// 区间内出现字符种类数
int type=0;
// 区间内字符出现了k次或k次以上的种类数
int kCount=0;
// 左右指针
int left=0, right=0;
// 当右指针小于数组长度
while(right<arr.length){
// 当前右指针指向字符
int cr = arr[right]-'a';
// 如果当前字符个数为0，说明首次出现，type加一
if(count[cr]==0) type++;
// 更新当前字符出现次数
count[cr]++;
// 如果出现次数等于k，kCount加一
if(count[cr]==k) kCount++;
// 如果type等于kCount，当前为合理区间
if(type==kCount) res=Math.max(res,right-left+1);
// 如果type大于i，说明区间内字符种类数超过范围
// 移动左区间，减少字符种类数
while(type>i){
// 左指针指向的字符
int cl=arr[left]-'a';
// 如果该字符出现次数等于k，当左指针划过后，个数将小于k
// kCount减一
if(count[cl]==k) kCount--;
// 更新该字符出现次数
count[cl]--;
// 如果该字符出现次数为0，type减一
if(count[cl]==0) type--;
left++;
}
right++;
}
}
return res;
} 本题解法执行时间为10ms。
Runtime: 10 ms, faster than 34.03% of Java online submissions for Longest Substring with At Least K Repeating Characters.
Memory Usage: 42.2 MB, less than 10.00% of Java online submissions for Longest Substring with At Least K Repeating Characters.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-395-longest-substring-with-at-least-k-repeating-characters-解题思路分析/