from collections import defaultdict # handle character frequency mapping
def get_substrings_with_k_distinct(s, k):
list_of_substrings = []
n = len(s)
# Iterate over all possible starting points of substrings
for i in range(n):
freq_map = defaultdict(int) # Dictionary to count character frequencies
distinct_count = 0 # Counter for distinct characters in current substring
# Extend the substring from position i to j
for j in range(i, n):
char = s[j] # Current character
# If character is new to the substring, increment distinct count
if freq_map[char] == 0:
distinct_count += 1
freq_map[char] += 1 # Update frequency of the character
# If we have exactly k distinct characters, store the substring
if distinct_count == k:
list_of_substrings.append(s[i:j+1])
# If we exceed k distinct characters, stop exploring this substring
elif distinct_count > k:
break
return list_of_substrings
string = "characters"
k = 4
substrings = get_substrings_with_k_distinct(string, k)
print("Number of substrings with exactly k distinct characters = ", len(substrings))
print(f"\nSubstrings with exactly {k} distinct characters in '{string}':")
for sub in substrings:
print(sub)
"""
run:
Number of substrings with exactly k distinct characters = 9
Substrings with exactly 4 distinct characters in 'characters':
char
chara
charac
harac
aract
ract
acte
cter
ters
"""
