// Function to get all substrings with exactly k distinct characters
function getSubstringsWithKDistinct(s: string, k: number): string[] {
const listOfSubstrings: string[] = [];
const n: number = s.length;
// Iterate over all possible starting points of substrings
for (let i = 0; i < n; i++) {
const freqMap: Map<string, number> = new Map(); // Map for character frequencies
let distinctCount = 0; // Counter for distinct characters
// Extend the substring from position i to j
for (let j = i; j < n; j++) {
const ch: string = s[j];
// If character is new to the substring, increment distinct count
if (!freqMap.has(ch)) {
distinctCount++;
freqMap.set(ch, 0);
}
freqMap.set(ch, (freqMap.get(ch) ?? 0) + 1);
// If we have exactly k distinct characters, store the substring
if (distinctCount === k) {
listOfSubstrings.push(s.slice(i, j + 1));
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinctCount > k) {
break;
}
}
}
return listOfSubstrings;
}
const str: string = "characters";
const k: number = 4;
const substrings: string[] = getSubstringsWithKDistinct(str, k);
console.log(`Number of substrings with exactly ${k} distinct characters = ${substrings.length}\n`);
console.log(`Substrings with exactly ${k} distinct characters in '${str}':`);
for (const sub of substrings) {
console.log(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
*/
