#include <stdio.h>
#include <string.h>
#define MAX_SUBSTRINGS 1024
#define MAX_LEN 128
// Function to get all substrings with exactly k distinct characters
int getSubstringsWithKDistinct(const char *s, int k, char substrings[MAX_SUBSTRINGS][MAX_LEN]) {
int count = 0;
int n = strlen(s);
// Iterate over all possible starting points of substrings
for (int i = 0; i < n; i++) {
int freq_map[256] = {0}; // array for character frequencies
int distinct_count = 0; // counter for distinct characters
// Extend the substring from position i to j
for (int j = i; j < n; j++) {
unsigned char ch = s[j];
// If character is new to the substring, increment distinct count
if (freq_map[ch] == 0) {
distinct_count++;
}
freq_map[ch]++;
// If we have exactly k distinct characters, store the substring
if (distinct_count == k) {
int length = j - i + 1;
if (count < MAX_SUBSTRINGS && length < MAX_LEN) {
strncpy(substrings[count], s + i, length);
substrings[count][length] = '\0'; // null terminate
count++;
}
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinct_count > k) {
break;
}
}
}
return count;
}
int main() {
const char *str = "characters";
int k = 4;
char substrings[MAX_SUBSTRINGS][MAX_LEN];
int numsubstrings = getSubstringsWithKDistinct(str, k, substrings);
printf("Number of substrings with exactly %d distinct characters = %d\n\n", k, numsubstrings);
printf("Substrings with exactly %d distinct characters in '%s':\n", k, str);
for (int i = 0; i < num; i++) {
printf("%s\n", substrings[i]);
}
return 0;
}
/*
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
*/
