首页 > 试题广场 >

长度为 K 的重复字符子串

[编程题]长度为 K 的重复字符子串

热度指数：7763 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $2 \le k \le 400$ , $5\le n \le 900$

进阶：时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

示例1

输入

"createfunonyoka",4

输出

示例2

输入

"yokagames",3

输出

示例3

输入

"yoka",4

输出

算法知识视频讲解

C/C++

敖星星

把字符串看成一条长为n的线，一个长为k的毛毛虫从线上爬过去，初始位置为[0,k-1]
  用双循环检查毛毛虫内部有没有重复的字母,有就跳过双循环，答案+1
    毛毛虫向前爬一步（left+1和right+1）
       直到爬到终点(right == n)
    int numKLenSubstrRepeats(string s, int k)
    {
        int left = 0,right = k-1;
        int ans = 0;
        int n = s.size();
        bool YN = false;
        while(right != n)
        {
            for(int i=left;i<=right;i++)
            {
                for(int j=i+1;j<=right;j++)
                {
                    if(s[i] == s[j])
                    {
                        ans++;
                        YN=true;
                        break;
                    }
                }
                if(YN)
                {
                    YN = false;
                    break;
                }
            }
            left++;
            right++;
        }
        return ans;
    }

发表于 2021-09-14 15:48:38 回复(1)

牛客941970663号

javascript解法

先得知道，‘abcde’分3块的有abc，bcd，cde 这3种分法，类推得到公式：字符串长度-要分的长度+1

然后遍历字符串得到所有的结果，将每一份变成数组，判断是否有重复数据

functionnumKLenSubstrRepeats(s, k) {

// write code here

let len = s.length;

let all = len - k + 1;

let res = [];

let a = 0;

for(let i = 0; i < all; i++) {

let mys = s.slice(i, i + k);

res.push(mys.split(''));

}

for(let i = 0; i < res.length; i++) {

let myarry = [...newSet(res[i])];

if(myarry.length !== res[i].length) {

a ++;

}

myarry = null;

}

returna;

}

发表于 2021-09-09 15:29:34 回复(0)

一念永恒201907311824587

滑动窗口以k为窗口的大小滑动窗口中需要判断是否有重复数组使用 set判断

    public int numKLenSubstrRepeats (String s, int k) {
        // write code here
        int n = s.length();
        int res = 0;
        Set<Character> set = new HashSet<>();
        for(int i = k-1; i < n; i++){
            for(int j = 0; j < k; j++){
                set.add(s.charAt(i-j));
            }
            if(set.size() < k){
                res++;
            }
            set.clear();
        }
        return res;
    }

发表于 2021-09-22 15:48:58 回复(0)

Python

发个offer就摆烂

利用 set() 浅显易懂

class Solution:
    def numKLenSubstrRepeats(self , s , k ):
        # write code here
        num = 0
        for i in range(len(s)-k+1):
            if len(set(s[i:i+k])) < k:
                num += 1
        return num

发表于 2022-01-15 23:05:43 回复(0)

C/C++

不偷不抢安度因_

不需要set去重，用一个变量记录重复的元素种类就行

int numKLenSubstrRepeats(string s, int k) {
    // T(n) = O(n), S(n) = O(n)
    if (k == 0) {
        return 0;
    }

    int l = 0;
    int repeated = 0;
    int n = s.size();
    unordered_map<char, int> mp;
    int ret = 0;

    for (int r = 0; r < n; ++r) {
        mp[s[r]]++;
        if (mp[s[r]] == 2) {
            ++repeated;
        }
        if (k > 0) {
            --k;
        } else {
            mp[s[l]]--;
            if (mp[s[l]] == 1) {
                --repeated;
            }
            ++l;
        }

        if (k == 0 && repeated > 0) {
            ++ret;
        }
    }

    return ret;
}

编辑于 2021-10-28 11:12:48 回复(0)

Java

BlueProtocol

public class NumKLenSubstrRepeats {
	public int numKLenSubstrRepeats(String s, int k) {
		// write code here
		// 问题一：如何判断最后一串数字
		Set<Character> set = new HashSet<>();
		char[] chars = s.toCharArray();
		int count = 0;
		for (int i = 0; i <= chars.length - k; i++) {
			set.add(chars[i]);
			for (int j = i + 1; j < i + k; j++) {
				if (!set.contains(chars[j])) {
					set.add(chars[j]);
					continue;
				} else {
					count++;
					break;
				}
			}
			set.clear();
		}
		return count;
	}
}

发表于 2022-10-10 09:27:42 回复(0)

C++

AsherChi

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    unordered_map<char, int> hash;
    
    bool check()
    {
        // 判断是否有出现两次的字符
        for(auto iter = hash.begin(); iter != hash.end(); iter++)
        {
            if(iter->second > 1)
                return true;
        }
        return false;    
    }
    
    int numKLenSubstrRepeats(string s, int k) {
        // write code here
        int len = s.length();
        int left = 0, right = 0;
        int res = 0;
        while(right < len)
        {
            // 记录出现过的字符次数
            hash[s[right]]++;
            // 间隔为给定的大小时 查询是否出现两次
            if(right-left >= k-1)
            {
                // 判断是否有出现两次的字符
                if(check())
                    res++;
                // 指针右移 对应出现的字符次数减一
                hash[s[left++]]--;
            }
            right++;
        }
        return res;
    }
};

发表于 2022-08-22 10:20:22 回复(0)

Java

blue&&lan

public int numKLenSubstrRepeats (String s, int k) {
        Set<Character> t=new HashSet<>();
        int c=0;
        for(int i=0;i<s.length()-k+1;i++){
            int j=i;
            while(j<i+k){
                t.add(s.charAt(j++));
            }
            if(t.size()<k)c++;
            while(!t.isEmpty()){
                t.clear();
            }
        }
        return c;
    }

发表于 2022-05-23 18:10:55 回复(1)

牛客499848474号

🐶卡桌游，蒸蒸日下🤣

发表于 2025-01-01 20:27:55 回复(0)

在努力存钱的外卷侠很胆小

class Solution:

def numKLenSubstrRepeats(self , s: str, k: int) -> int:

# write code here

n=len(s)

num=0

for i in range(n-k+1):

if len(set(s[i:i+k]))<len(s[i:i+k]):

num+=1

return num

发表于 2024-12-27 16:03:07 回复(0)

牛客883572022号

function numKLenSubstrRepeats( s ,  k ) {
    // write code here
    let left = 0 
    let right = k 
    let count = 0 
    while(right <= s.length){
        let arr = s.slice(left, right).split('')
        let set = new Set(arr)
        if(arr.length > set.size) count ++ 
        left ++ 
        right ++ 
    }
    return count 
}

发表于 2024-10-18 13:19:50 回复(0)

唐氏综合征

8岁李琛优雅解法：

public static int numKLenSubstrRepeats(String s, int k) {
        if (k > s.length()) return 0;

        int res = 0;
        int[] dict = new int[26];

        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            dict[c]++;

            if (i >= k) {
                int shiftC = s.charAt(i - k) - 'a';
                dict[shiftC]--;
            }

            // 不能只看 c, 还要看窗口内部剩余的是否有重复， 比如 funone, 4
            if (i >= k - 1)
                for (int e : dict)
                    if (e > 1) {
                        res++;
                        break;
                    }
        }
        return res;
    }

发表于 2024-07-16 14:07:27 回复(0)

Python3

liangzhengjie

双指针解法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param k int整型 
# @return int整型
#
class Solution:
    def numKLenSubstrRepeats(self, s: str, k: int) -> int:
        # write code here
        print(s)
        res = 0

        count = [0 for i in range(26)]
        repeat_chr = {}
        for i in range(min(k, len(s))):
            index = ord(s[i])-ord('a')
            count[index] += 1
            if count[index] > 1:
                repeat_chr[s[i]] = count[index]
        if len(repeat_chr) > 0:
            res += 1
        left = 0
        right = k

        while right < len(s):
            count[ord(s[left])-ord('a')] -= 1
            if s[left] in repeat_chr:
                if repeat_chr[s[left]] <= 2:
                    repeat_chr.pop(s[left])
                else:
                    repeat_chr[s[left]] -= 1
            left += 1

            count[ord(s[right])-ord('a')] += 1
            if count[ord(s[right])-ord('a')] > 1:
                repeat_chr[s[right]] = count[ord(s[right])-ord('a')]
            right += 1

            if len(repeat_chr) > 0:
                res += 1

        return res

发表于 2024-05-06 00:55:34 回复(0)

牛客2024007号

之前写过不重复子串数，这题刚好是那题的逆问题。直接把那题代码拿过来了，结果用所有子串数做个减法就行了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int numKLenSubstrRepeats (String s, int k) {
        // write code here
        HashMap<Character, Integer> map = new HashMap<>();
        int right = 0;
        int left = 0;
        int res = 0;
        while(right < s.length()) {
            int times = map.getOrDefault(s.charAt(right), 0);
            if(right - left + 1 > k || times > 0) {
                map.put(s.charAt(left), map.get(s.charAt(left)) - 1);
                left++;
                continue;
            }
            map.put(s.charAt(right), times + 1);
            if(right - left + 1 == k) res++;
            right++;
        }
        return  s.length() - k + 1 - res;
    }
}

发表于 2024-01-14 22:11:38 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param k int整型 
     * @return int整型
     */
    public int numKLenSubstrRepeats (String s, int k) {
        // write code here
        int sum=0;
        ArrayList<Character> list=new ArrayList<>();
        //依次进行判断
        for(int i=0;i+k<=s.length();i++){
            //如果该截取的字符串有重复的就sum++
            if(dc(s.substring(i,i+k))==true){
                sum++;
            }
        }
        return sum;
    }
    public boolean dc(String str){
        //HashSet进行查重
        HashSet<Character> set=new HashSet<>();
        for(int i=0;i<str.length();i++){
            if(!set.contains(str.charAt(i))){
                set.add(str.charAt(i));
            }else{
            //有重复
                return true;
            }
        }
        //无重复
        return false;
    }
}

发表于 2023-05-18 18:24:44 回复(0)

冰糖狮子头

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param s string字符串

# @param k int整型

# @return int整型

from collections import defaultdict

class Solution:

def numKLenSubstrRepeats(self , s , k ):

res = 0

for i in range(len(s)-k+1):

str = s[i:k+i]

dic = defaultdict(int)

for char in str:

if dic[char]==0:

dic[char] = 1

elif dic[char]==1:

dic[char]+=1

res += 1

break

return res

发表于 2023-04-22 11:38:23 回复(0)

小谷围做题家

package main

import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @param k int整型 
 * @return int整型
*/
func numKLenSubstrRepeats( s string ,  k int ) int {
    cnt:=map[byte]int{}
    ans:=0
    for i,ch:=range []byte(s){
        if i==k{
            break
        }
        cnt[ch]++
    }
    if len(cnt)<k{
        ans++
    }
    for l,r:=0,k;r<len(s);l,r=l+1,r+1{
        var key byte
        key=byte(s[l])
        if cnt[key]==1{
            delete(cnt,key)
        }else{
            cnt[key]--
        }
        key=byte(s[r])
        cnt[key]++
        if len(cnt)<k{
            ans++
        }
    }
    return ans
}

发表于 2023-03-07 18:33:09 回复(0)

在喝茶的咸鱼很温柔

class Solution:
    def numKLenSubstrRepeats(self , s , k ):
        # write code here
        a=0
        for i in range(len(s)-k+1):
            if len(set(s[i:i+k]))<k:
                a+=1
        return a

发表于 2023-02-08 14:49:02 回复(0)

丶supreme丶

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param k int整型
     * @return int整型
     */
    public int numKLenSubstrRepeats (String s, int k) {
        // write code here
        int ans = 0, flag = 0;
        int[] cnts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            if (++cnts[s.charAt(i) - 'a'] == 2) ++flag;
            if (i < k - 1) continue;
            if (i >= k && --cnts[s.charAt(i - k) - 'a'] == 1) --flag;
            if (flag > 0) ++ans;
        }
        return ans;
    }
}

发表于 2023-01-13 23:51:00 回复(0)

在刷题的大白菜很爱吃

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param s string字符串

# @param k int整型

# @return int整型

class Solution:

def numKLenSubstrRepeats(self , s , k ):

count = 0

i = 0

for i in range(0,len(s)):

if i+k < len(s) + 1 :

l = len(s[i:i+k])

set1 = set(s[i:i+k])

list1 = list(set1)

if l != len(list1):

i += 1

count += 1

else:

i += 1

continue

else:

break

return count

发表于 2022-11-06 15:46:31 回复(0)

提交观点

问题信息

字符串双指针

上传者：小小

难度：

44条回答 179收藏 7432浏览

通过挑战的用户

查看代码

Nancytoday

2023-02-24 22:22:59
牛客91896...

2022-11-10 10:38:07
Notprofect

2022-11-03 17:27:49
617530038

2022-11-03 13:46:02
法兰西多士

2022-11-03 13:26:06

长度为 K 的重复字符子串

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题