Problem Statement:

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:

The logic is that we store the number of words ending at each vowel in a variable. The pseudocode is this:

 
a, e, i, o, u = e, a+i, a+e+o+u, i+u, a

This happens each time we wish to increase size of word by one. The final answer is a+e+i+o+u. We add modulus operators for every addition to avoid overflow and also while returning the sum.

 
class Solution {
public:
    int countVowelPermutation(int n) 
    {
        int mod=1e9+7;
        vector<int> A = {1,1,1,1,1};
        for(int i=1; i<n; i++)
            A = {A[1], \
                (A[0]+A[2])%mod, \
                (((A[0]+A[1])%mod+A[3])%mod+A[4])%mod, \
                (A[2]+A[4])%mod, \
                A[0]};
        return ((((A[0]+A[1])%mod+A[2])%mod+A[3])%mod+A[4])%mod;
    }
};

$TC: O(n)$, $SC: O(1)$