#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
// Function to get all substrings with exactly k distinct characters
std::vector<std::string> getSubstringsWithKDistinct(const std::string& s, int k) {
std::vector<std::string> list_of_substrings;
int n = s.length();
// Iterate over all possible starting points of substrings
for (int i = 0; i < n; ++i) {
std::unordered_map<char, int> freq_map; // Map to count character frequencies
int distinct_count = 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 (freq_map[ch] == 0) {
++distinct_count;
}
++freq_map[ch]; // Update frequency of the character
// If we have exactly k distinct characters, store the substring
if (distinct_count == k) {
list_of_substrings.push_back(s.substr(i, j - i + 1));
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinct_count > k) {
break;
}
}
}
return list_of_substrings;
}
int main() {
std::string str = "characters";
int k = 4;
std::vector<std::string> substrings = getSubstringsWithKDistinct(str, k);
std::cout << "Number of substrings with exactly k distinct characters = " << substrings.size() << "\n";
std::cout << "\nSubstrings with exactly " << k << " distinct characters in '" << str << "':" << "\n";
for (const std::string& sub : substrings) {
std::cout << sub << "\n";
}
}
/*
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
*/
