1100. Find K-Length Substrings With No Repeated Characters

1100. Find K-Length Substrings With No Repeated Characters

https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/leetcode.com

Given a string S, return the number of substrings of length K with no repeated characters.

Example 1:

Input: S = "havefunonleetcode", K = 5
Output: 6
Explanation: 
There are 6 substrings they are : 'havef','avefu','vefun','efuno','etcod','tcode'.

Example 2:

Input: S = "home", K = 5
Output: 0
Explanation: 
Notice K can be larger than the length of S. In this case is not possible to find any substring.

Note:

1. 1 <= S.length <= 10^4

2. All characters of S are lowercase English letters.

3. 1 <= K <= 10^4

思路：

维护一个固定大小的sliding window，可以每移动一次就检验一次window内是否重复，但这样计算成本太高了，不如记录重复字符数，<=0的时候就判定没重复，res++

class Solution:
    def numKLenSubstrNoRepeats(self, S: str, K: int) -> int:
        if K > len(S): return 0
        res = 0
        repeat = 0
        freq = defaultdict(int)
        
        i = 0
        while i < len(S):
            if freq[S[i]] > 0:
                repeat += 1
                
            freq[S[i]] += 1
            
            if i >= K:
                if freq[S[i-K]] > 1:
                    repeat -= 1
                freq[S[i-K]] -= 1
                
            if repeat <= 0 and i >= K-1:
                print(S[i+1-K:i+1])
                res += 1
                
            i += 1
            
        return res