Skip to main content
Back to problems
#1220
Hard Algorithms

Count vowels permutation

Dynamic Programming
61.4% acceptance
Feb 25, 2026
3296
220
Given an integer n, your task is to count how many strings of length n can be formed under the following rules: Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u') Each vowel 'a' may only be followed by an 'e'. Each vowel 'e' may only be followed by an 'a' or an 'i'. Each vowel 'i' may not be followed by another 'i'. Each vowel 'o' may only be followed by an 'i' or a 'u'. Each vowel 'u' may only be followed by an 'a'. Since the answer may be too large, return it modulo 10^9 + 7.

Solution

Rust
Time O(n)
Space O(1)
LeetCode
solution.rs
impl Solution {
  pub fn count_vowel_permutation(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let (mut a, mut e, mut i, mut o, mut u) = (1i64, 1i64, 1i64, 1i64, 1i64);
    for _ in 1..n {
      let na = (e + i + u) % MOD;
      let ne = (a + i) % MOD;
      let ni = (e + o) % MOD;
      let no = i % MOD;
      let nu = (i + o) % MOD;
      a = na; e = ne; i = ni; o = no; u = nu;
    }
    ((a + e + i + o + u) % MOD) as i32
  }
}