// Function to get all substrings with exactly k distinct characters
function getSubstringsWithKDistinct(string $s, int $k): array {
$list_of_substrings = [];
$n = strlen($s);
// Iterate over all possible starting points of substrings
for ($i = 0; $i < $n; $i++) {
$freq_map = []; // associative array for character frequencies
$distinct_count = 0; // counter for distinct characters
// Extend the substring from position i to j
for ($j = $i; $j < $n; $j++) {
$ch = $s[$j];
// If character is new to the substring, increment distinct count
if (!isset($freq_map[$ch])) {
$distinct_count++;
$freq_map[$ch] = 0;
}
$freq_map[$ch]++;
// If we have exactly k distinct characters, store the substring
if ($distinct_count == $k) {
$list_of_substrings[] = substr($s, $i, $j - $i + 1);
}
// If we exceed k distinct characters, stop exploring this substring
elseif ($distinct_count > $k) {
break;
}
}
}
return $list_of_substrings;
}
$str = "characters";
$k = 4;
$substrings = getSubstringsWithKDistinct($str, $k);
echo "Number of substrings with exactly $k distinct characters = " . count($substrings) . PHP_EOL;
echo PHP_EOL;
echo "Substrings with exactly $k distinct characters in '$str':" . PHP_EOL;
foreach ($substrings as $sub) {
echo $sub . PHP_EOL;
}
/*
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
*/
