Count of substrings containing every vowel and k consonants ii

Hash Table String Sliding Window

40.6% acceptance

Feb 23, 2026

992

148

You are given a string word and a non-negative integer k. Return the total number of substrings of word that contain every vowel ('a', 'e', 'i', 'o', and 'u') at least once and exactly k consonants.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_of_substrings(word: String, k: i32) -> i64 {
    fn at_least(word: &[u8], k: i64) -> i64 {
      let mut vowels = [0i32; 5];
      let mut distinct = 0i32;
      let mut cons = 0i64;
      let mut left = 0;
      let mut count = 0i64;
      let vowel_idx = |c: u8| match c {
        b'a' => Some(0), b'e' => Some(1), b'i' => Some(2),
        b'o' => Some(3), b'u' => Some(4), _ => None,
      };
      for right in 0..word.len() {
        if let Some(i) = vowel_idx(word[right]) {
          if vowels[i] == 0 { distinct += 1; }
          vowels[i] += 1;
        } else {
          cons += 1;
        }
        while cons >= k && distinct == 5 {
          count += (word.len() - right) as i64;
          if let Some(i) = vowel_idx(word[left]) {
            vowels[i] -= 1;
            if vowels[i] == 0 { distinct -= 1; }
          } else {
            cons -= 1;
          }
          left += 1;
        }
      }
      count
    }
    let w = word.as_bytes();
    at_least(w, k as i64) - at_least(w, k as i64 + 1)
  }
}