Count beautiful substrings ii

Hash Table Math String Number Theory Prefix Sum

26.8% acceptance

Feb 25, 2026

214

You are given a string s and a positive integer k. Let vowels and consonants be the number of vowels and consonants in a string. A string is beautiful if: vowels == consonants. (vowels * consonants) % k == 0, in other terms the multiplication of vowels and consonants is divisible by k. Return the number of non-empty beautiful substrings in the given string s. A substring is a contiguous sequence of characters in a string. Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'. Consonant letters in English are every letter except vowels.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_substrings(s: String, k: i32) -> i64 {
    use std::collections::HashMap;

    let bytes = s.as_bytes();
    let _n = bytes.len();

    // Find smallest p s.t. p^2 % k == 0 (min valid vowel count)
    let mut p = 1usize;
    while (p * p) as i32 % k != 0 {
      p += 1;
    }
    let period = 2 * p; // required length multiple

    // Convert to +1 (vowel) / -1 (consonant)
    // prefix[i] = running balance
    // Condition: prefix[j] == prefix[i] AND (j - i) % period == 0
    // Group by (prefix_val, i % period)

    let mut prefix = 0i32;
    let mut cnt: HashMap<(i32, usize), i64> = HashMap::new();
    cnt.insert((0, 0), 1);

    let mut ans = 0i64;
    for (idx, &c) in bytes.iter().enumerate() {
      if b"aeiou".contains(&c) {
        prefix += 1;
      } else {
        prefix -= 1;
      }
      let key = (prefix, (idx + 1) % period);
      let e = cnt.entry(key).or_insert(0);
      ans += *e;
      *e += 1;
    }
    ans
  }
}