import java.util.Map;
import java.util.List;
import java.util.HashMap;
import java.util.ArrayList;
public class SubstringWithKDistinct {
// Function to get all substrings with exactly k distinct characters
public static List<String> getSubstringsWithKDistinct(String s, int k) {
List<String> listOfSubstrings = new ArrayList<>();
int n = s.length();
// Iterate over all possible starting points of substrings
for (int i = 0; i < n; i++) {
Map<Character, Integer> freqMap = new HashMap<>(); // 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.charAt(j); // Current character
// If character is new to the substring, increment distinct count
if (!freqMap.containsKey(ch)) {
distinctCount++;
}
// Update frequency of the character
freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
// If we have exactly k distinct characters, store the substring
if (distinctCount == k) {
listOfSubstrings.add(s.substring(i, j + 1));
}
// If we exceed k distinct characters, stop exploring this substring
else if (distinctCount > k) {
break;
}
}
}
return listOfSubstrings;
}
public static void main(String[] args) {
String str = "characters";
int k = 4;
List<String> substrings = getSubstringsWithKDistinct(str, k);
System.out.println("Number of substrings with exactly k distinct characters = " + substrings.size());
System.out.println("\nSubstrings with exactly " + k + " distinct characters in '" + str + "':");
for (String sub : substrings) {
System.out.println(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
*/
