题解 | #长度为 K 的重复字符子串#

长度为 K 的重复字符子串

http://www.nowcoder.com/practice/eced9a8a4b6c42b79c95ae5625e1d5fd

题意整理

给定一个由小写字母组成的长度为n的字符串S，找出所有长度为k且包含重复字符的子串。
返回全部满足要求的子串的数目。

方法一（字符串截取）

1.解题思路

遍历整个字符串，依次截取长度为k的子串。
每次判断子串是否包含重复字符，如果包含，则计数加1。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int numKLenSubstrRepeats (String s, int k) {
        int res=0;
        int n=s.length();
        for(int i=0;i<n-k+1;i++){
            //得到每一个长度为k的子串
            String sub=s.substring(i,i+k);
            //判断是否包含重复字符
            if(check(sub)){
                res++;
            }
        }
        return res;
    }
    
    //判断是否包含重复字符
    private boolean check(String sub){
        int[] cnt=new int[26];
        //遍历子串，并记录字符出现次数
        for(char c:sub.toCharArray()){
            cnt[c-'a']++;
        }
        
        for(char c:sub.toCharArray()){
            //如果某字符出现次数超过1，说明重复了
            if(cnt[c-'a']>1){
                return true;
            }
        }
        return false;
        
    }
}

3.复杂度分析

时间复杂度：需要遍历 $n - k + 1$ 个子串，每次截取的时间复杂度为 $O (k)$ ，对于每一个子串，判断是否重复的时间复杂度为 $O (k)$ ，所以最终的时间复杂度是 $O (n * k^{2})$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（滑动窗口）

1.解题思路

定义滑动窗口的长度为k，遍历整个字符串。
每次统计滑动窗口内各个字符出现的次数，如果有重复，则res加1。每次都将窗口右移，当前字符次数加1，开头字符次数减1，从而跟新窗口内各个字符出现的次数。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int numKLenSubstrRepeats (String s, int k) {
        int res=0;
        int n=s.length();
        int[] cnt=new int[26];
        //第一个长度为k的子串，将对应字符出现次数记录在cnt数组
        for(int i=0;i<k;i++){
            cnt[s.charAt(i)-'a']++;
        }
        //如果重复，则res加1
        if(check(cnt)) res++;
        for(int i=k;i<n;i++){
            //每次窗口右移，当前字符次数加1，开头字符次数减1
            cnt[s.charAt(i)-'a']++;
            cnt[s.charAt(i-k)-'a']--;
            //如果重复，则res加1
            if(check(cnt)){
                res++;
            }
        }
        return res;
    }
    
    //用于判断是否包含重复字符
    private boolean check(int[] cnt){
        for(int i=0;i<26;i++){
            if(cnt[i]>1){
                return true;
            }
        }
        return false;
        
    }
}