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

Hints:
Use dynamic programming.
Let dp[i][j] be the number of strings of length i that ends with the j-th vowel.
Deduce the recurrence from the given relations between vowels.

Counting the Vowel Permutation using Dynamic Programming Algorithm

Let’s define d[i][j] a two dimension array (or vector) that stores the count for length i and end with the j-th vowel. Thus, the j is ranged from 0 to 4 – for [‘a’, ‘e’, ‘i’, ‘o’, ‘u’].

The initial values can be set for single vowel, which is dp[1][0..4] = 1. Then, we can loop from size 2 to n, then, based on the rules, only summing up those valid permutations.

The answer may be large, thus we need to apply the MOD operator to the intermediate values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int countVowelPermutation(int n) {
        vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0));
        for (int i = 0; i < 5; ++ i) {
            dp[1][i] = 1;
        }
        const int MOD = 1000000007;
        for (int i = 2; i <= n; ++ i) {
            dp[i][0] = (dp[i - 1][1] + // ea
                       dp[i - 1][2] + // ia                                   
                       dp[i - 1][4]) % MOD;  // ua
            dp[i][1] = (dp[i - 1][0] + // ae                                   
                       dp[i - 1][2]) % MOD;  // ie
            dp[i][2] = (dp[i - 1][1] + // ei
                       dp[i - 1][3]) % MOD;  // oi
            dp[i][3] = dp[i - 1][2];  // io                                  
            dp[i][4] = (dp[i - 1][2] + // iu
                       dp[i - 1][3]) % MOD;  // ou                                               
        }
        return (dp.back()[0] + 
            dp.back()[1] +
            dp.back()[2] +
            dp.back()[3] +
            dp.back()[4]) % MOD;          
    }
};

class Solution {
public:
    int countVowelPermutation(int n) {
        vector<vector<int64_t>> dp(n + 1, vector<int64_t>(5, 0));
        for (int i = 0; i < 5; ++ i) {
            dp[1][i] = 1;
        }
        const int MOD = 1000000007;
        for (int i = 2; i <= n; ++ i) {
            dp[i][0] = (dp[i - 1][1] + // ea
                       dp[i - 1][2] + // ia                                   
                       dp[i - 1][4]) % MOD;  // ua
            dp[i][1] = (dp[i - 1][0] + // ae                                   
                       dp[i - 1][2]) % MOD;  // ie
            dp[i][2] = (dp[i - 1][1] + // ei
                       dp[i - 1][3]) % MOD;  // oi
            dp[i][3] = dp[i - 1][2];  // io                                  
            dp[i][4] = (dp[i - 1][2] + // iu
                       dp[i - 1][3]) % MOD;  // ou                                               
        }
        return (dp.back()[0] + 
            dp.back()[1] +
            dp.back()[2] +
            dp.back()[3] +
            dp.back()[4]) % MOD;          
    }
};

The final solution will be the sum for the 5 values in dp[n][0..4]. Complexity: O(N) time and O(N) space.

–EOF (The Ultimate Computing & Technology Blog) —