Substring With At Least K Distinct Characters
franklinqin0 StringTwo Pointers
# Input & Output
@param s: a string
@param k: an integer
@return: the number of substrings there are that contain at least k distinct characters
1
2
3
2
3
# Solution
Let be the length of the string s
.
# Two Pointers
If the window s[left:right]
satisfy the loop invariant: has at least k
distinct characters, then add n - right
to res
(b/c these substrings definitely count), increment left
by , and see if the loop invariant still holds. If not, increment right
by .
Complexity
time:
space:
from collections import defaultdict
def kDistinctCharacters(self, s, k):
n = len(s)
hashmap = defaultdict(int)
left = 0
res = 0
for right in range(n):
right_char = s[right]
hashmap[right_char] += 1
while len(hashmap) >= k:
res += n - right
left_char = s[left]
hashmap[left_char] -= 1
if hashmap[left_char] == 0:
hashmap.pop(left_char)
left += 1
return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19