# Substring With At Least K Distinct Characters

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

## # Solution

Let $n$ 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 $1$, and see if the loop invariant still holds. If not, increment right by $1$.

Complexity

time: $O(n)$
space: $O(n)$

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