class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
}
};
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^4S 中的所有字符均为小写英文字母1 <= K <= 10^4原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 2 MB, 提交时间: 2023-10-17 20:20:28
func numKLenSubstrNoRepeats(s string, k int) int {
mem:=map[byte]int{}
n:=len(s)
l:=0
ans:=0
for i:=0;i<n;i++{
mem[s[i]]++
for l<i&&mem[s[i]]>1{
mem[s[l]]--
l++
}
if i-l+1==k{
ans++
mem[s[l]]--
l++
}
}
return ans
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-17 20:19:08
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
res = 0
for i in range(n - k + 1):
tmp = set(s[i : i + k])
if (len(tmp) == k):
res += 1
return res
java 解法, 执行用时: 19 ms, 内存消耗: 39.1 MB, 提交时间: 2023-10-17 20:18:24
class Solution {
public int numKLenSubstrNoRepeats(String S, int K) {
// 和无重复最长的子串类似，使用滑动窗口
int length = S.length();
int res = 0;
int left = 0;
Map<Character, Integer> window = new HashMap<>();
for (int right = 0; right < length; right++) {
char ch = S.charAt(right);
window.put(ch, window.getOrDefault(ch, 0) + 1);
// 添加的无重复，且窗口长度为K, 则累加，并将窗口整体右移，继续判断后面的
if (window.get(ch) == 1 && (right - left + 1 == K)) {
res++;
window.put(S.charAt(left), window.get(S.charAt(left)) - 1);
left++;
continue;
}
// 有重复则整体右移，直到把重复的那个给排除在外
while (window.get(ch) > 1) {
window.put(S.charAt(left), window.get(S.charAt(left)) - 1);
left++;
}
}
return res;
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 8 MB, 提交时间: 2023-10-17 20:18:07
class Solution {
public:
int numKLenSubstrNoRepeats(string S, int K) {
int res = 0;
if (S.size() < K) {
return 0;
}
unordered_map<char, int> mp;
for (int i = 0; i < K; i++) {
mp[S[i]]++;
}
if (mp.size() == K) {
res++;
}
for (int i = K; i < S.size(); i++) {
mp[S[i]]++;
mp[S[i - K]]--;
if (mp[S[i - K]] == 0) {
mp.erase(S[i - K]);
}
if (mp.size() == K) {
res++;
}
}
return res;
}
};