首页 > 试题广场 >

长度为 K 的重复字符子串

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

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

输入

"createfunonyoka",4

输出

4
示例2

输入

"yokagames",3

输出

1
示例3

输入

"yoka",4

输出

0
双指针解法
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @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)