Count sorted vowel strings

Math Dynamic Programming Combinatorics

79.2% acceptance

Feb 25, 2026

3932

Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted. A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_vowel_strings(n: i32) -> i32 {
    // C(n+4, 4) = stars and bars: place n stars among 5 vowel buckets
    // dp[j] = number of sorted strings of current length ending with vowel j
    let mut dp = [1i32; 5];
    for _ in 1..n {
      // prefix sum: dp[j] += dp[j-1] (can use vowel >= j)
      for j in 1..5 {
        dp[j] += dp[j - 1];
      }
    }
    dp.iter().sum()
  }
}