X

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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-340-longest-substring-with-at-most-k-distinct-characters-解题思路分析/
Categories: leetcode
kwantong:

View Comments (0)