给你一个字符串 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
方法一：双指针 + 计数器
我们观察发现，字符均为小写字母，也即最多有
接下来，我们用双指针
遍历字符串
遍历结束后，即可得到所有符合题意的子串的个数。
时间复杂度
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
if k > n or k > 26:
return 0
ans = j = 0
cnt = Counter()
for i, c in enumerate(s):
cnt[c] += 1
while cnt[c] > 1 or i - j + 1 > k:
cnt[s[j]] -= 1
j += 1
ans += i - j + 1 == k
return ansclass Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
n = len(s)
if k > n:
return 0
cnt = Counter(s[:k])
ans = int(len(cnt) == k)
for i in range(k, n):
cnt[s[i]] += 1
cnt[s[i - k]] -= 1
if cnt[s[i - k]] == 0:
cnt.pop(s[i - k])
ans += len(cnt) == k
return ansclass Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
int n = s.length();
if (k > n || k > 26) {
return 0;
}
int[] cnt = new int[128];
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
++cnt[s.charAt(i)];
while (cnt[s.charAt(i)] > 1 || i - j + 1 > k) {
cnt[s.charAt(j++)]--;
}
ans += i - j + 1 == k ? 1 : 0;
}
return ans;
}
}class Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
int n = s.length();
if (k > n) {
return 0;
}
Map<Character, Integer> cnt = new HashMap<>(k);
for (int i = 0; i < k; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
}
int ans = cnt.size() == k ? 1 : 0;
for (int i = k; i < n; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
if (cnt.merge(s.charAt(i - k), -1, Integer::sum) == 0) {
cnt.remove(s.charAt(i - k));
}
ans += cnt.size() == k ? 1 : 0;
}
return ans;
}
}class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
int n = s.size();
if (k > n || k > 26) {
return 0;
}
int cnt[128]{};
int ans = 0;
for (int i = 0, j = 0; i < n; ++i) {
++cnt[s[i]];
while (cnt[s[i]] > 1 || i - j + 1 > k) {
--cnt[s[j++]];
}
ans += i - j + 1 == k;
}
return ans;
}
};class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
int n = s.size();
if (k > n) {
return 0;
}
unordered_map<char, int> cnt;
for (int i = 0; i < k; ++i) {
cnt[s[i]]++;
}
int ans = cnt.size() == k ? 1 : 0;
for (int i = k; i < n; ++i) {
cnt[s[i]]++;
cnt[s[i - k]]--;
if (cnt[s[i - k]] == 0) {
cnt.erase(s[i - k]);
}
ans += cnt.size() == k ? 1 : 0;
}
return ans;
}
};func numKLenSubstrNoRepeats(s string, k int) (ans int) {
if k > len(s) || k > 26 {
return 0
}
cnt := [128]int{}
for i, j := 0, 0; i < len(s); i++ {
cnt[s[i]]++
for cnt[s[i]] > 1 || i-j+1 > k {
cnt[s[j]]--
j++
}
if i-j+1 == k {
ans++
}
}
return
}func numKLenSubstrNoRepeats(s string, k int) (ans int) {
n := len(s)
if k > n {
return 0
}
cnt := map[byte]int{}
for i := 0; i < k; i++ {
cnt[s[i]]++
}
if len(cnt) == k {
ans++
}
for i := k; i < n; i++ {
cnt[s[i]]++
cnt[s[i-k]]--
if cnt[s[i-k]] == 0 {
delete(cnt, s[i-k])
}
if len(cnt) == k {
ans++
}
}
return
}function numKLenSubstrNoRepeats(s: string, k: number): number {
const n = s.length;
if (k > n) {
return 0;
}
const cnt: Map<string, number> = new Map();
for (let i = 0; i < k; ++i) {
cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
}
let ans = cnt.size === k ? 1 : 0;
for (let i = k; i < n; ++i) {
cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
cnt.set(s[i - k], (cnt.get(s[i - k]) ?? 0) - 1);
if (cnt.get(s[i - k]) === 0) {
cnt.delete(s[i - k]);
}
ans += cnt.size === k ? 1 : 0;
}
return ans;
}class Solution {
/**
* @param String $s
* @param Integer $k
* @return Integer
*/
function numKLenSubstrNoRepeats($s, $k) {
$sum = ($k * ($k + 1)) / 2 - $k;
$cnt = $tmp = 0;
for ($i = 0; $i < strlen($s) - $k + 1; $i++) {
$str = substr($s, $i, $k);
for ($j = 0; $j < $k; $j++) {
$tmp += strpos($str, $str[$j]);
}
if ($tmp === $sum) {
$cnt++;
}
$tmp = 0;
}
return $cnt;
}
}