Count beautiful substrings i

Hash Table Math String Enumeration Number Theory Prefix Sum

61.0% acceptance

Feb 25, 2026

176

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(1)

LeetCode

solution.rs

impl Solution {
  pub fn beautiful_substrings(s: String, k: i32) -> i32 {
    let s: Vec<i32> = s.bytes().map(|c| if b"aeiou".contains(&c) { 1 } else { -1 }).collect();
    let n = s.len();
    let mut ans = 0;
    for i in 0..n {
      let mut sum = 0i32;
      let mut vowels = 0i32;
      for j in i..n {
        sum += s[j];
        if s[j] == 1 { vowels += 1; }
        // vowels == consonants: sum == 0 (equal counts); vowels = (j-i+1)/2
        if sum == 0 {
          let v = vowels;
          if (v * v) % k == 0 {
            ans += 1;
          }
        }
      }
    }
    ans
  }
}