1220. Count Vowels Permutation

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.

 

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3: 

Input: n = 5
Output: 68

 

Constraints:

  • 1 <= n <= 2 * 10^4

Rust Solution

struct Solution;

const MOD: i64 = 1_000_000_007;

impl Solution {
    fn count_vowel_permutation(n: i32) -> i32 {
        let n = n as usize;
        let mut a = vec![0; n];
        let mut e = vec![0; n];
        let mut i = vec![0; n];
        let mut o = vec![0; n];
        let mut u = vec![0; n];
        a[0] = 1;
        e[0] = 1;
        i[0] = 1;
        o[0] = 1;
        u[0] = 1;
        for j in 1..n {
            e[j] += a[j - 1];

            a[j] += e[j - 1];
            i[j] += e[j - 1];

            a[j] += i[j - 1];
            e[j] += i[j - 1];
            o[j] += i[j - 1];
            u[j] += i[j - 1];

            i[j] += o[j - 1];
            u[j] += o[j - 1];

            a[j] += u[j - 1];

            a[j] %= MOD;
            e[j] %= MOD;
            i[j] %= MOD;
            o[j] %= MOD;
            u[j] %= MOD;
        }
        ((a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD) as i32
    }
}

#[test]
fn test() {
    let n = 1;
    let res = 5;
    assert_eq!(Solution::count_vowel_permutation(n), res);
    let n = 2;
    let res = 10;
    assert_eq!(Solution::count_vowel_permutation(n), res);
    let n = 5;
    let res = 68;
    assert_eq!(Solution::count_vowel_permutation(n), res);
}

Having problems with this solution? Click here to submit an issue on github.