Description#
Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.
Example 1:
Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.
Example 2:
Input: s = "home", k = 5
Output: 0
Explanation: Notice k can be larger than the length of s. In this case, it is not possible to find any substring.
Constraints:
1 <= s.length <= 104s consists of lowercase English letters.1 <= k <= 104
Solutions#
Solution 1: Two Pointers + Counter#
We observe that all characters are lowercase letters, so there are at most $26$ different characters. Therefore, if $k > 26$ or $k > n$, it is impossible to find any substring of length $k$ without repeated characters, and we can directly return $0$.
Next, we use two pointers $j$ and $i$ to maintain a sliding window, where $j$ is the left endpoint of the sliding window, $i$ is the right endpoint of the sliding window, and a counter $cnt$ is used to count the number of occurrences of each character in the sliding window.
We traverse the string $s$, each time adding $s[i]$ to the sliding window, i.e., $cnt[s[i]]++$. If at this time $cnt[s[i]] > 1$ or $i - j + 1 > k$, then we loop to remove $s[j]$ from the sliding window, i.e., $cnt[s[j]]–$, and move $j$ to the right. If after moving $j$ to the right, the window size $i - j + 1$ is exactly equal to $k$, it means that the string in the sliding window is a substring that meets the requirements of the problem, and we increment the result by one.
After the traversal ends, we can get the number of all substrings that meet the requirements of the problem.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string $s$, and $C$ is the size of the character set. In this problem, $C = 26$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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 ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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;
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class 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 ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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
}
|
