##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1220.html

# 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

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/
// 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;
}
};

• class Solution {
public int countVowelPermutation(int n) {
final int MODULO = 1000000007;
long[][] dp = new long[n][5];
Arrays.fill(dp[0], 1);
for (int i = 1; i < n; i++) {
dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % MODULO;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MODULO;
dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % MODULO;
dp[i][3] = dp[i - 1][2];
dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % MODULO;
}
long sum = 0;
for (int i = 0; i < 5; i++)
sum += dp[n - 1][i];
int count = (int) (sum % MODULO);
return count;
}
}

############

class Solution {
private static final long MOD = (long) 1e9 + 7;

public int countVowelPermutation(int n) {
long[] dp = new long[5];
long[] t = new long[5];
Arrays.fill(dp, 1);
for (int i = 0; i < n - 1; ++i) {
t[0] = (dp[1] + dp[2] + dp[4]) % MOD;
t[1] = (dp[0] + dp[2]) % MOD;
t[2] = (dp[1] + dp[3]) % MOD;
t[3] = dp[2];
t[4] = (dp[2] + dp[3]) % MOD;
System.arraycopy(t, 0, dp, 0, 5);
}
long ans = 0;
for (int i = 0; i < 5; ++i) {
ans = (ans + dp[i]) % MOD;
}
return (int) ans;
}
}

• // OJ: https://leetcode.com/problems/count-vowels-permutation/
// 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;
}
};

• class Solution:
def countVowelPermutation(self, n: int) -> int:
dp = (1, 1, 1, 1, 1)
MOD = 1000000007
for _ in range(n - 1):
dp = (
(dp[1] + dp[2] + dp[4]) % MOD,
(dp[0] + dp[2]) % MOD,
(dp[1] + dp[3]) % MOD,
dp[2],
(dp[2] + dp[3]) % MOD,
)
return sum(dp) % MOD

############

# 1220. Count Vowels Permutation
# https://leetcode.com/problems/count-vowels-permutation/

class Solution:
def countVowelPermutation(self, n: int):
M = 10 ** 9 + 7
a = e = i = o = u = 1

for _ in range(2, n+1):
a,e,i,o,u = e, a+i, a+e+o+u, i+u, a

return (a+e+i+o+u) % M

• func countVowelPermutation(n int) int {
const mod int = 1e9 + 7
dp := [5]int{1, 1, 1, 1, 1}
for i := 0; i < n-1; i++ {
dp = [5]int{
(dp[1] + dp[2] + dp[4]) % mod,
(dp[0] + dp[2]) % mod,
(dp[1] + dp[3]) % mod,
dp[2],
(dp[2] + dp[3]) % mod,
}
}
ans := 0
for _, v := range dp {
ans = (ans + v) % mod
}
return ans
}

• /**
* @param {number} n
* @return {number}
*/
var countVowelPermutation = function (n) {
const mod = 1000000007;
const dp = new Array(5).fill(1);
const t = new Array(5).fill(0);
for (let i = 0; i < n - 1; ++i) {
t[0] = (dp[1] + dp[2] + dp[4]) % mod;
t[1] = (dp[0] + dp[2]) % mod;
t[2] = (dp[1] + dp[3]) % mod;
t[3] = dp[2];
t[4] = (dp[2] + dp[3]) % mod;
dp.splice(0, 5, ...t);
}
let ans = 0;
for (let i = 0; i < 5; ++i) {
ans = (ans + dp[i]) % mod;
}
return ans;
};