# 1100. Find K-Length Substrings With No Repeated Characters

{% embed url="<https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/>" %}

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++

```python
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
```
