题意整理

  • 给定一个由小写字母组成的长度为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.复杂度分析

  • 时间复杂度:需要遍历nk+1n-k+1个子串,每次截取的时间复杂度为O(k)O(k),对于每一个子串,判断是否重复的时间复杂度为O(k)O(k),所以最终的时间复杂度是O(nk2)O(n*k^2)
  • 空间复杂度:需要额外常数级别的空间,所以空间复杂度为O(1)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;
        
    }
}

3.复杂度分析

  • 时间复杂度:只需遍历整个字符串一次,所以时间复杂度是O(n)O(n)
  • 空间复杂度:需要额外常数级别的空间,所以空间复杂度为O(1)O(1)