1220. Count Vowels Permutation

Description of Problem

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

Solution

Tags: Dynamic Programming Recurrence

Explanation

Very simple: A string end with a produces a string end with e and so on.

a -> e
e -> a i
i -> a e o u
o -> i u
u -> a

In other words

a' = e + i + u
e' = a + i
i' = e + o
o' = i
u' = i + o

[**]Remember to do modulo for each addition in order to prevent overflow.

[***] Most of answer written in Rust in LeetCode requires casting (from i64 to i32). This solution requires none.

Code (Rust) - Clean Code

impl Solution {
    pub fn count_vowel_permutation(n: i32) -> i32 {
        let modulo = 1_000_000_007;
        let addition = |a,b|(a + b) % modulo ;

        let mut a = 1;
        let mut e = 1;
        let mut i = 1;
        let mut o = 1;
        let mut u = 1;

        let mut a_next = 1;
        let mut e_next = 1;
        let mut i_next = 1;
        let mut o_next = 1;
        let mut u_next = 1;

        for _ in 2..=n {
            a_next = [e, i, u].into_iter().fold(0, addition) % modulo; 
            e_next = (a + i) % modulo;
            i_next = (e + o) % modulo;
            o_next = i % modulo;
            u_next = (i + o) % modulo;

            // replace old values
            a = a_next;
            e = e_next;
            i = i_next;
            o = o_next;
            u = u_next;
        }

        return [a_next, e_next, i_next, o_next, u_next].into_iter().fold(0, addition) % modulo;
    }
}

Code (Rust) - Dirty Code but may be faster

impl Solution {
    pub fn count_vowel_permutation(n: i32) -> i32 {
        let modulo = 1_000_000_007;

        let mut a = 1;
        let mut e = 1;
        let mut i = 1;
        let mut o = 1;
        let mut u = 1;

        let mut a_next = 1;
        let mut e_next = 1;
        let mut i_next = 1;
        let mut o_next = 1;
        let mut u_next = 1;

        for _ in 2..=n {
            a_next = ( (e + i) % modulo  + u ) % modulo; 
            e_next = ( a + i ) % modulo;
            i_next = ( e + o ) % modulo;
            o_next = ( i ) % modulo;
            u_next = ( i + o ) % modulo;

            // replace old values
            a = a_next;
            e = e_next;
            i = i_next;
            o = o_next;
            u = u_next;
        }

        return (((((((a_next + e_next)% modulo) + i_next) % modulo) + o_next) % modulo) + u_next) % modulo;
    }
}

Complexity

Time Complexity

• \(T(n) = \Theta(n)\)

Auxiliary Space

• \(S(n) = O(1)\)