首页 > 试题广场 >

长度为 K 的重复字符子串

[编程题]长度为 K 的重复字符子串
  • 热度指数:6994 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给你一个由小写字母组成的长度为n的字符串 S ,找出所有长度为 k 且包含重复字符的子串,请你返回全部满足要求的子串的数目

数据范围: ,
进阶: 时间复杂度,空间复杂度
示例1

输入

"createfunonyoka",4

输出

4
示例2

输入

"yokagames",3

输出

1
示例3

输入

"yoka",4

输出

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)