using System;
using System.Collections.Generic;
class SubstringWithKDistinct
{
// Function to get all substrings with exactly k distinct characters
static List<string> GetSubstringsWithKDistinct(string s, int k) {
var listOfSubstrings = new List<string>();
int n = s.Length;
// Iterate over all possible starting points of substrings
for (int i = 0; i < n; i++) {
var freqMap = new Dictionary<char, int>(); // Map to count character frequencies
int distinctCount = 0; // Counter for distinct characters in current substring
// Extend the substring from position i to j
for (int j = i; j < n; j++) {
char ch = s[j]; // Current character
// If character is new to the substring, increment distinct count
if (!freqMap.ContainsKey(ch)) {
distinctCount++;
freqMap[ch] = 1;
}
else {
freqMap[ch]++;
}
// If we have exactly k distinct characters, store the substring
if (distinctCount == k) {
listOfSubstrings.Add(s.Substring(i, j - i + 1));
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinctCount > k) {
break;
}
}
}
return listOfSubstrings;
}
static void Main()
{
string str = "characters";
int k = 4;
List<string> substrings = GetSubstringsWithKDistinct(str, k);
Console.WriteLine($"Number of substrings with exactly k distinct characters = {substrings.Count}\n");
Console.WriteLine($"Substrings with exactly {k} distinct characters in '{str}':");
foreach (string sub in substrings)
{
Console.WriteLine(sub);
}
}
}
/*
run:
Number of substrings with exactly k distinct characters = 9
Substrings with exactly 4 distinct characters in 'characters':
char
chara
charac
harac
aract
ract
acte
cter
ters
*/
