README.md

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

English Version

题目描述

给你一个字符串 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. 1 <= S.length <= 10^4
2. S 中的所有字符均为小写英文字母
3. 1 <= K <= 10^4

解法

固定大小的滑动窗口。

Python3

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        ans = j = 0
        mp = {}
        for i, c in enumerate(s):
            if c in mp:
                j = max(j, mp[c] + 1)
            mp[c] = i
            if i - j + 1 >= k:
                ans += 1
        return ans

Java

class Solution {
    public int numKLenSubstrNoRepeats(String s, int k) {
        int ans = 0;
        Map<Character, Integer> mp = new HashMap<>();
        for (int i = 0, j = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (mp.containsKey(c)) {
                j = Math.max(j, mp.get(c) + 1);
            }
            mp.put(c, i);
            if (i - j + 1 >= k) {
                ++ans;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i = 0, j = 0; i < s.size(); ++i)
        {
            char c = s[i];
            if (mp.count(c)) j = max(j, mp[c] + 1);
            mp[c] = i;
            if (i - j + 1 >= k) ++ans;
        }
        return ans;
    }
};

Go

func numKLenSubstrNoRepeats(s string, k int) int {
	mp := make(map[rune]int)
	ans, j := 0, 0
	for i, c := range s {
		if v, ok := mp[c]; ok {
			j = max(j, v+1)
		}
		mp[c] = i
		if i-j+1 >= k {
			ans++
		}
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

...