LC1100.长度为K的无重复字符子串

1. 题目

• 1100. 长度为 K 的无重复字符子串

给你一个字符串S，找出所有长度为K且不含重复字符的子串，请你返回全部满足要求的子串的数目 。

示例 1：

**输入：** S = "havefunonleetcode", K = 5
**输出：** 6
**解释：** 
这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。

示例 2：

**输入：** S = "home", K = 5
**输出：** 0
**解释：** 
注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。

提示：

• 1 <= S.length <= 10^4
• S 中的所有字符均为小写英文字母
• 1 <= K <= 10^4

2. 思路

• 提前调整好第一个窗口：提前预处理第一个窗口，[0, k - 1] 这个闭区间内，逐个遍历，然后判定哈希表的 KV 数量是否等于 k，即可判定窗口内容是否合法。
• 如何判定窗口合法：如果在动态调整过程中，窗口内某个 KV 的 V == 0，那么，就移除该键值对，最后，通过判定 KV 键值对规模是否为 k，校验当前窗口合法性。

3. 代码如下

func numKLenSubstrNoRepeats(s string, k int) int {
    n := len(s)

    if n < k {
        return 0
    }

    cnt := make(map[byte]int)
    ans := 0

    // first window
    for i := 0; i < k; i++ {
        cur := s[i]
        cnt[cur] ++
    }

    // check first window valid
    if len(cnt) == k {
        ans++
    }

    // sliding window
    for right := k; right < n; right++ {
        left := right - k 
        
        prev, cur := s[left], s[right]

        // handle remvoe
        cnt[prev]--
        if cnt[prev] == 0 {
            delete(cnt, prev)
        }

        // handle add
        cnt[cur]++

        if len(cnt) == k {
            ans++
        }
    }

    return ans
}