// Function to get all substrings with exactly k distinct characters
fn get_substrings_with_k_distinct(s: &str, k: usize) -> Vec<String> {
let mut list_of_substrings = Vec::new();
let n = s.len();
let bytes = s.as_bytes(); // work with bytes for indexing
// Iterate over all possible starting points of substrings
for i in 0..n {
let mut freq_map = std::collections::HashMap::new(); // map for character frequencies
let mut distinct_count = 0; // counter for distinct characters
// Extend the substring from position i to j
for j in i..n {
let ch = bytes[j];
// If character is new to the substring, increment distinct count
if !freq_map.contains_key(&ch) {
distinct_count += 1;
freq_map.insert(ch, 0);
}
*freq_map.get_mut(&ch).unwrap() += 1;
// If we have exactly k distinct characters, store the substring
if distinct_count == k {
list_of_substrings.push(s[i..=j].to_string());
}
// If we exceed k distinct characters, stop exploring this substring
else if distinct_count > k {
break;
}
}
}
list_of_substrings
}
fn main() {
let s = "characters";
let k = 4;
let substrings = get_substrings_with_k_distinct(s, k);
println!(
"Number of substrings with exactly {} distinct characters = {}\n",
k,
substrings.len()
);
println!(
"Substrings with exactly {} distinct characters in '{}':",
k, s
);
for sub in substrings {
println!("{}", sub);
}
}
/*
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
*/
