LEETCODE 340. Longest Substring with At Most K Distinct Characters 解题思路分析

题目大意：

至多包含 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.