using System;
using System.Collections.Generic;
public class Program
{
public static int CountSubstringWithKDistinctChars(string s, int k) {
int count = 0;
for (int i = 0; i < s.Length; i++) {
char ch = s[i];
string tmp = "" + ch;
ISet<char> set = new HashSet<char>();
set.Add(ch);
for (int j = i + 1; j < s.Length; j++) {
char next_ch = s[j];
set.Add(next_ch);
tmp += next_ch;
if (tmp.Length >= k && set.Count == k) {
count++;
}
}
}
return count;
}
public static void Main(string[] args)
{
string str = "characters";
int k = 4;
Console.Write("Number of substrings with exactly k distinct characters = ");
Console.Write(CountSubstringWithKDistinctChars(str, k));
}
}
/*
run:
Number of substrings with exactly k distinct characters = 9
*/
