X

LEETCODE 395. Longest Substring with At Least K Repeating Characters 解题思路分析

题目大意:

至少有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种字符的情况下的合理最长子串。遍历每一种情况时,我们需要定义如下几个变量:

  1. 数组count[],统计当前子串中每种字符出现的次数
  2. type,当前子串中出现字符的种类数
  3. 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-解题思路分析/
Categories: leetcode
kwantong: