给你一个由小写字母组成的长度为n的字符串 S ,找出所有长度为 k 且包含重复字符的子串,请你返回全部满足要求的子串的数目。
数据范围:
,
进阶: 时间复杂度
,空间复杂度)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @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