1220

1220. Count Vowels Permutation (Hard)

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

Companies:
Amazon

Related Topics:
Dynamic Programming

Solution 1. DP

Given the rule, the valid combinations are as follows:

a: ae
e: ea ei
i: ia ie io iu
o: oi ou
u: ua

Let dp[i][j] be the count of valid strings of length i ending with letter j where 0 < i <= n, j = 'a', 'e', 'i', 'o', 'u'.

So we have

dp[i]['a'] = dp[i - 1]['e'] + dp[i - 1]['i'] + dp[i - 1]['u']
dp[i]['e'] = dp[i - 1]['a'] + dp[i - 1]['i']
dp[i]['i'] = dp[i - 1]['e'] + dp[i - 1]['o']
dp[i]['o'] = dp[i - 1]['i']
dp[i]['u'] = dp[i - 1]['i'] + dp[i - 1]['o']

dp[1][j] = 1

The answer is Sum{ dp[n][j] | j = 'a', 'e', 'i', 'o', 'u' }.

// OJ: https://leetcode.com/problems/count-vowels-permutation/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int countVowelPermutation(int n) {
        int mod = 1e9 + 7, a = 1, e = 1, i = 1, o = 1, u = 1;
        while (--n) {
            int aa = ((e + i) % mod + u) % mod;
            int ee = (a + i) % mod;
            int ii = (e + o) % mod;
            int oo = i;
            int uu = (i + o) % mod;
            a = aa, e = ee, i = ii, o = oo, u = uu;
        }
        return ((((a + e) % mod + i) % mod + o) % mod + u) % mod;
    }
};

Or

// OJ: https://leetcode.com/problems/count-vowels-permutation/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int countVowelPermutation(int n) {
        long mod = 1e9 + 7, a = 1, e = 1, i = 1, o = 1, u = 1;
        while (--n) {
            long aa = e;
            long ee = (a + i) % mod;
            long ii = ((a + e) % mod + (o + u) % mod) % mod;
            long oo = (i + u) % mod;
            long uu = a;
            a = aa, e = ee, i = ii, o = oo, u = uu;
        }
        return (((((a + e) % mod + i) % mod) + o) % mod + u) % mod;
    }
};