import Foundation
// Function to get all substrings with exactly k distinct characters
func getSubstringsWithKDistinct(_ s: String, _ k: Int) -> [String] {
var listOfSubstrings: [String] = []
let n = s.count
let characters = Array(s) // convert to array for indexing
// Iterate over all possible starting points of substrings
for i in 0..<n {
var freqMap: [Character: Int] = [:] // dictionary for character frequencies
var distinctCount = 0 // counter for distinct characters
// Extend the substring from position i to j
for j in i..<n {
let ch = characters[j]
// If character is new to the substring, increment distinct count
if freqMap[ch] == nil {
distinctCount += 1
freqMap[ch] = 0
}
freqMap[ch]! += 1
// If we have exactly k distinct characters, store the substring
if distinctCount == k {
let substring = String(characters[i...j])
listOfSubstrings.append(substring)
}
// If we exceed k distinct characters, stop exploring this substring
else if distinctCount > k {
break
}
}
}
return listOfSubstrings
}
let str = "characters"
let k = 4
let substrings = getSubstringsWithKDistinct(str, k)
print("Number of substrings with exactly \(k) distinct characters = \(substrings.count)\n")
print("Substrings with exactly \(k) distinct characters in '\(str)':")
for sub in substrings {
print(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
*/
