package main
import (
"fmt"
)
// Function to get all substrings with exactly k distinct characters
func getSubstringsWithKDistinct(s string, k int) []string {
var listOfSubstrings []string
n := len(s)
// Iterate over all possible starting points of substrings
for i := 0; i < n; i++ {
freqMap := make(map[byte]int) // map for character frequencies
distinctCount := 0 // counter for distinct characters
// Extend the substring from position i to j
for j := i; j < n; j++ {
ch := s[j]
// If character is new to the substring, increment distinct count
if _, exists := freqMap[ch]; !exists {
distinctCount++
freqMap[ch] = 0
}
freqMap[ch]++
// If we have exactly k distinct characters, store the substring
if distinctCount == k {
listOfSubstrings = append(listOfSubstrings, s[i:j+1])
} else if distinctCount > k {
// If we exceed k distinct characters, stop exploring this substring
break
}
}
}
return listOfSubstrings
}
func main() {
str := "characters"
k := 4
substrings := getSubstringsWithKDistinct(str, k)
fmt.Printf("Number of substrings with exactly %d distinct characters = %d\n\n", k, len(substrings))
fmt.Printf("Substrings with exactly %d distinct characters in '%s':\n", k, str)
for _, sub := range substrings {
fmt.Println(sub)
}
}
/*
run:
Number of substrings with exactly 4 distinct characters = 9
Substrings with exactly 4 distinct characters in 'characters':
char
chara
charac
harac
aract
ract
acte
cter
ters
*/
