首页 > 试题广场 >

长度为 K 的重复字符子串

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

热度指数：6913 时间限制：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)

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)

一念永恒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)

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)

牛客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)

C++

牛客622914227号

bool isCover(unordered_map<char, int>&mp){
        for(auto & it:mp){
            if(it.second>1){
                return true;
            }
        }
        return false;
    }
    //20220728，类似覆盖子串;
    int numKLenSubstrRepeats(string s, int k) {
        unordered_map<char, int>mp;
        int left=0,right=0;
        int res=0;
        while(right<s.size()){
            mp[s[right]]++;
            //满足的条件中(含有重复子串),逐渐移动左指针，找到长度为k的子串
            while(right-left+1 >=k && isCover(mp)){
                if(right-left+1 ==k){
                    res++;
                }
                mp[s[left]]--;
                left++;
            }
            right++;
        }
        return res;
    }

发表于 2022-07-28 23:42:04 回复(2)

Python 3

来牛客玩玩

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

发表于 2022-07-06 23:17:26 回复(0)

Python 3

danspace

class Solution:
    def numKLenSubstrRepeats(self , s , k ):
        # write code here
        count = 0
        l = 0
        while l+k <= len(s):
            sub = s[l:l+k]
            # 检查是否有重复字符
            repeated = False
            d = {}
            for ch in sub:
                if ch in d:
                    repeated = True
                    break
                else:
                    d[ch] = 1
            if repeated:
                count += 1
            l += 1
        return count

发表于 2022-04-21 17:17:15 回复(0)

做机器学习的化工侠

哈希表解法

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;
        int n = s.length();
        if(k>n)
            return 0;
        HashMap<Character,Integer> h = new HashMap<Character,Integer>();
        for(int i=0; i < k; i++){
            if(h.containsKey(s.charAt(i))){
                h.put(s.charAt(i),h.get(s.charAt(i))+1);
            }else{
                h.put(s.charAt(i),1);
            }
        }
        if(h.size()<k)
            ans++;
        // 开启循环
        for(int i=k; i < n; i++){
            //出表
            if(h.get(s.charAt(i-k))==1){
                h.remove(s.charAt(i-k));
            }else{
                h.put(s.charAt(i-k),h.get(s.charAt(i-k))-1);
            }
            //进表
            if(h.containsKey(s.charAt(i))){
                h.put(s.charAt(i),h.get(s.charAt(i))+1);
            }else{
                h.put(s.charAt(i),1);
            }
            // 统计
            if(h.size()<k)
                ans++;
        }
        return ans;
    }
}

发表于 2022-03-16 09:37:09 回复(0)

ZeusHong

利用set容器不会插入重复元素的特性，进行遍历搜索。

int numKLenSubstrRepeats(string s, int k) {
    int cnt = 0;//子串个数
    //设置滑动窗口边界
    int left = 0;//左边界，初始化为0
    int right = k - 1;//右边界，初始化为k-1
    set<char> searchBlock;//滑动窗口，即长度为k的子串
    for(int i = 0; i < s.length() - k + 1; i++)
    {
        for(int j = left; j <= right; j++)
        {
            searchBlock.insert(s[j]);//将长度为k的子串插入到set容器中
        }
        if(searchBlock.size() < k)//若set容器中的元素个数小于k，则说明其中含有重复元素，计数+1
        {
            cnt++;
        }
        left++;//滑块窗口向右移动
        right++;//滑块窗口向右移动
        searchBlock.clear();//清空滑动窗口
    }
    return cnt;
}

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

提交观点

问题信息

字符串双指针

上传者：小小

难度：

39条回答 162收藏 5205浏览

通过挑战的用户

查看代码

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 的重复字符子串

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题