The original article is available at https://dawnmagnet.top/leetcode/2022/01/17/.

Given an integer n, count how many strings of length n can be formed according to these rules:

Every character in the string must be a lowercase vowel ('a', 'e', 'i', 'o', 'u').

• Every 'a' must be followed by an 'e'.
• Every 'e' must be followed by an 'a' or an 'i'.
• An 'i' cannot be followed by another 'i'.
• Every 'o' must be followed by an 'i' or a 'u'.
• Every 'u' must be followed by an 'a'.

Because the answer may be large, return it modulo 10^9 + 7.

Example 1:

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

Example 2:

**Input:** n = 2
**Output:** 10
**Explanation:** The 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

Source: LeetCode Link: https://leetcode-cn.com/problems/count-vowels-permutation Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis

#

This problem is mainly about recognizing a pattern. More formally, it can be solved with dynamic programming, but the recurrence is quite simple.

From the rules, we can see that the possible extensions of a vowel sequence depend only on its final character. We do not need to know the entire prefix; knowing its last character is enough to extend it. Therefore, a single array can store the number of sequences ending in each of a, e, i, o, and u, which greatly simplifies the computation.

By deriving the transitions from the conditions, we obtain:

• a can be preceded by e, i, or u.
• e can be preceded by a or i.
• i can be preceded by e or o.
• o can be preceded by i.
• u can be preceded by i or o.

These transitions give the recurrence. Once we compute the number of sequences ending in each of a, e, i, o, and u for the requested length, add them to obtain the answer.

Rust Code

#

const m: i64 = 1_000_000_007;
impl Solution {
    pub fn count_vowel_permutation(n: i32) -> i32 {
        let mut c = [1i64, 1, 1, 1, 1];
        for i in 1..n {
            c = [
                (c[1] + c[2] + c[4]) % m,
                (c[0] + c[2]) % m,
                (c[1] + c[3]) % m,
                c[2],
                (c[2] + c[3]) % m,
            ];
        }
        (c.iter().sum::<i64>() % m) as i32
    }
}