// Function to get all substrings with exactly k distinct characters
fun getSubstringsWithKDistinct(s: String, k: Int): List<String> {
val listOfSubstrings = mutableListOf<String>()
val n = s.length
// Iterate over all possible starting points of substrings
for (i in 0 until n) {
val freqMap = mutableMapOf<Char, Int>() // map for character frequencies
var distinctCount = 0 // counter for distinct characters
// Extend the substring from position i to j
for (j in i until n) {
val ch = s[j]
// If character is new to the substring, increment distinct count
if (ch !in freqMap) {
distinctCount++
freqMap[ch] = 0
}
freqMap[ch] = freqMap[ch]!! + 1
// If we have exactly k distinct characters, store the substring
if (distinctCount == k) {
listOfSubstrings.add(s.substring(i, j + 1))
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinctCount > k) {
break
}
}
}
return listOfSubstrings
}
fun main() {
val str = "characters"
val k = 4
val substrings = getSubstringsWithKDistinct(str, k)
println("Number of substrings with exactly $k distinct characters = ${substrings.size}\n")
println("Substrings with exactly $k distinct characters in '$str':")
substrings.forEach { println(it) }
}
/*
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
*/
