# 1220. Count Vowels Permutation

## Description

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

## Solutions

Solution 1: Dynamic Programming

Based on the problem description, we can list the possible subsequent vowels for each vowel:

a [e]
e [a|i]
i [a|e|o|u]
o [i|u]
u [a]


From this, we can deduce the possible preceding vowels for each vowel:

[e|i|u]	a
[a|i]	e
[e|o]	i
[i]	o
[i|o]	u


We define $f[i]$ as the number of strings of the current length ending with the $i$-th vowel. If the length is $1$, then $f[i]=1$.

When the length is greater than $1$, we define $g[i]$ as the number of strings of the current length ending with the $i$-th vowel. Then $g[i]$ can be derived from $f$, that is:

$g[i]= \begin{cases} f[1]+f[2]+f[4] & i=0 \\ f[0]+f[2] & i=1 \\ f[1]+f[3] & i=2 \\ f[2] & i=3 \\ f[2]+f[3] & i=4 \end{cases}$

The final answer is $\sum_{i=0}^{4}f[i]$. Note that the answer may be very large, so we need to take the modulus of $10^9+7$.

The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string, and $C$ is the number of vowels. In this problem, $C=5$.

Solution 2: Matrix Exponentiation to Accelerate Recursion

The time complexity is $O(C^3 \times \log n)$, and the space complexity is $O(C^2)$. Here, $C$ is the number of vowels. In this problem, $C=5$.

• class Solution {
public int countVowelPermutation(int n) {
long[] f = new long[5];
Arrays.fill(f, 1);
final int mod = (int) 1e9 + 7;
for (int i = 1; i < n; ++i) {
long[] g = new long[5];
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f = g;
}
long ans = 0;
for (long x : f) {
ans = (ans + x) % mod;
}
return (int) ans;
}
}

• class Solution {
public:
int countVowelPermutation(int n) {
using ll = long long;
vector<ll> f(5, 1);
const int mod = 1e9 + 7;
for (int i = 1; i < n; ++i) {
vector<ll> g(5);
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f = move(g);
}
return accumulate(f.begin(), f.end(), 0LL) % mod;
}
};

• class Solution:
def countVowelPermutation(self, n: int) -> int:
f = [1] * 5
mod = 10**9 + 7
for _ in range(n - 1):
g = [0] * 5
g[0] = (f[1] + f[2] + f[4]) % mod
g[1] = (f[0] + f[2]) % mod
g[2] = (f[1] + f[3]) % mod
g[3] = f[2]
g[4] = (f[2] + f[3]) % mod
f = g
return sum(f) % mod


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

• function countVowelPermutation(n: number): number {
const f: number[] = Array(5).fill(1);
const mod = 1e9 + 7;
for (let i = 1; i < n; ++i) {
const g: number[] = Array(5).fill(0);
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f.splice(0, 5, ...g);
}
return f.reduce((a, b) => (a + b) % mod);
}


• /**
* @param {number} n
* @return {number}
*/
var countVowelPermutation = function (n) {
const mod = 1e9 + 7;
const f = Array(5).fill(1);
for (let i = 1; i < n; ++i) {
const g = Array(5).fill(0);
g[0] = (f[1] + f[2] + f[4]) % mod;
g[1] = (f[0] + f[2]) % mod;
g[2] = (f[1] + f[3]) % mod;
g[3] = f[2];
g[4] = (f[2] + f[3]) % mod;
f.splice(0, 5, ...g);
}
return f.reduce((a, b) => (a + b) % mod);
};