object SubstringsWithKDistinct {
// Function to get all substrings with exactly k distinct characters
def getSubstringsWithKDistinct(s: String, k: Int): List[String] = {
val n = s.length
var listOfSubstrings = List.empty[String]
// Iterate over all possible starting points of substrings
for (i <- 0 until n) {
val freqMap = scala.collection.mutable.Map.empty[Char, Int] // map for character frequencies
var distinctCount = 0 // counter for distinct characters
// Extend the substring from position i to j
for (j <- i until n) {
val ch = s(j)
// If character is new to the substring, increment distinct count
if (!freqMap.contains(ch)) {
distinctCount += 1
freqMap(ch) = 0
}
freqMap(ch) = freqMap(ch) + 1
// If we have exactly k distinct characters, store the substring
if (distinctCount == k) {
listOfSubstrings = listOfSubstrings :+ s.substring(i, j + 1)
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinctCount > k) {
// break out of inner loop
}
}
}
listOfSubstrings
}
def main(args: Array[String]): Unit = {
val str = "characters"
val k = 4
val substrings = getSubstringsWithKDistinct(str, k)
println(s"Number of substrings with exactly $k distinct characters = ${substrings.length}\n")
println(s"Substrings with exactly $k distinct characters in '$str':")
substrings.foreach(println)
}
}
/*
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
*/
