给你一个由小写字母组成的长度为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