题目大意：
至多包含 K 个不同字符的最长子串
给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。
示例1：
输入: s = "eceba", k = 2 输出: 3 解释: 则 T 为 “ece”，所以长度为 3。
示例2：
输入: s = “aa”, k = 1 输出: 2 解释: 则 T 为 “aa”，所以长度为 2。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=340
解题思路分析：
这道题需要用到双指针，定义两个指针left和right代表当前区间，初始时默认两个指针的位置都在下标0处。另外定义一个map，记录区间内出现过的每个字符的数量。最后在定义一个变量distinct代表当前区间内字符的种类数。
开始时，先向右移动右指针，先查看map中右指针指向字符的个数，如果为0，说明该字符第一次出现，变量distinct加一，同时更新map中该字符的数量加一。如果此时distinct小于等于k，说明当前区间为一个合理区间，用当前区间的长度更新全局最大值。反之，如果distinct大于k，说明该区间不合理，我们需要减少该区间内字符种类，这时我们需要向右移动左指针，左指针指向的字符代表将会被移除出区间，因此，此时map中该字符数量需要减一，减一操作后，如果该字符数量为0，说明该字符已经从区间内消失，此时distinct减一（减一后distinct应该等于k），并结束移动左指针，返回继续移动右指针。直到右指针到达字符串尾部，统计出的最大合理区间长度即是返回结果。
实现代码：
public int lengthOfLongestSubstringKDistinct(String s, int k) {
// 如果字符串长度为0或者k为0，返回0
if(s.length()==0 || k==0) return 0;
// 将字符串转为字符数组
char[] arr = s.toCharArray();
// 区间内字符种类
int distinct = 0;
// 记录区间内出现过的每种字符的个数
Map<Character, Integer> count=new HashMap<>();
// 左指针
int left=0;
// 返回结果
int res=0;
// 从0向右移动右指针
for(int right=0;right<arr.length;right++){
// 当前右指针字符
char rightChar=arr[right];
// 查看该字符在区间内的个数
int c = count.getOrDefault(rightChar,0);
// 个数为0，说明当前是第一次出现，字符种类加一
if(c==0) distinct++;
// 更新当前字符在区间内出现的次数
count.put(rightChar, c+1);
// 如果字符种类小于等于k，当前区间为合理区间
if(distinct<=k){
// 更新合理区间最大值
res=Math.max(res, right-left+1);
}else{
// 当前为非合理区间
while(distinct>k){
// 左指针指向的字符
char leftChar=arr[left];
// 该字符区间内出现的次数
int leftCount = count.getOrDefault(leftChar,0);
// 移除该字符
count.put(leftChar,leftCount-1);
// 如果该字符数量为0，说明区间内不在包含该字符
// 字符种类减一
if(leftCount-1==0) distinct--;
// 否则继续移动左指针
left++;
}
}
}
return res;
} 本题解法执行时间为11ms。
Runtime: 11 ms, faster than 71.63% of Java online submissions for Longest Substring with At Most K Distinct Characters.
Memory Usage: 38.3 MB, less than 65.96% of Java online submissions for Longest Substring with At Most K Distinct Characters.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-340-longest-substring-with-at-most-k-distinct-characters-解题思路分析/
View Comments (0)