# [1100. Find K-Length Substrings With No Repeated Characters](https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/)
##### tags: `leetcode`

[TOC]

## Description
Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.

**example**

## **Ideas**
* Slide window
repeat:
1. 判斷window內的值有無重複
2. 往下移一格
### Way 1
* 因為輸入的值皆為lowercase English letters，當k > 26時可以直接return 0
* 建立一個unordered_map<char, int> cnt來計算長度為k的string
* 判斷substring是否符合條件，接著往右位移一格
* cnt.size() = k
* TC=O(n), SC=O(1)
* Python3 版本

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        if k > 26:
            return 0
        count = Counter(s[:k])
        res = 0
        for i in range(len(s) - k):
            if len(count) == k:
                res += 1
            if count[s[i]] == 1:
                del count[s[i]]
            else:
                count[s[i]] -= 1
            count[s[i+k]] += 1
        
        return res + int(len(count)==k)

* cpp版本

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        if(k > 26)return 0;
        
        int res = 0, n = s.size();
        unordered_map<char, int> cnt;
        /*
        在這裡錯了一次，還是不熟悉cpp...
        原本寫i < k，可是n可能會小於k
        改成i < min(n, k)
        */
        for(int i = 0; i < min(n, k); ++i) { // 先計算 s[0:k]
            ++cnt[s[i]];
        }
        for(int l = 0, r = k; r < n; ++r, ++l) {
            if (cnt.size() == k){ 
                ++res;
            }
            
            if (cnt[s[l]] == 1) {
                cnt.erase(s[l]);
            } else {
                --cnt[s[l]];
            }
            
            ++cnt[s[r]];
        }
        return res + (cnt.size() == k);
    }
};

### Way 2
* 想辦法優化，其實也參考了解答XD
* unordered_map的部分刪減花費時間還是太久
* 決定改成兩個pointers left, right
* 改成用int cnt[26] = {0}儲存
* 並且直接判斷 s[left: right+1].size() == k就可以了

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        if (k > 26) return 0;
        int res = 0, n = s.size();
        int left = 0, right = 0;
        int cnt[26] = {0};
        
        while (right < n) {
            ++cnt[s[right] - 'a'];
            
            while (cnt[s[right] - 'a'] > 1) {
                --cnt[s[left++] - 'a'];
            }
            if (right - left + 1 == k) {
                ++res;
                --cnt[s[left++] - 'a'];
            }
            ++right;
        }
        return res;
    }
};