Algorithm
Problem Name: 1220. Count Vowels Permutation
Problem Link: https://leetcode.com/problems/count-vowels-permutation/
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
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int countVowelPermutation(int n) {
long aCount = 1;
long eCount = 1;
long iCount = 1;
long oCount = 1;
long uCount = 1;
final int MOD = 1000000007;
for (int i = 1; i < n; i++) {
long aCountNew = (eCount + iCount + uCount) % MOD;
long eCountNew = (aCount + iCount) % MOD;
long iCountNew = (eCount + oCount) % MOD;
long oCountNew = (iCount) % MOD;
long uCountNew = (iCount + oCount) % MOD;
aCount = aCountNew;
eCount = eCountNew;
iCount = iCountNew;
oCount = oCountNew;
uCount = uCountNew;
}
long result = (aCount + eCount + iCount + oCount + uCount) % MOD;
return (int) result;
}
}
Input
n = 1
Output
5
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const countVowelPermutation = function (n) {
const mod = 1e9 + 7
const arr = [
[0, 1, 1], // a -> e
[0, 1, 2], // e -> a, i
[0, 1, 4], // i -> a, e, o, u
[0, 1, 2], // o -> i, u
[0, 1, 1], // u -> a
]
for (let i = 3; i < = n; i++) {
arr[0][i % 3] = arr[1][(i - 1) % 3] % mod
arr[1][i % 3] = (arr[0][(i - 1) % 3] + arr[2][(i - 1) % 3]) % mod
arr[2][i % 3] =
(arr[0][(i - 1) % 3] +
arr[1][(i - 1) % 3] +
arr[3][(i - 1) % 3] +
arr[4][(i - 1) % 3]) %
mod
arr[3][i % 3] = (arr[2][(i - 1) % 3] + arr[4][(i - 1) % 3]) % mod
arr[4][i % 3] = arr[0][(i - 1) % 3] % mod
}
return arr.reduce((sum, subArr) => sum + subArr[n % 3], 0) % mod
}
Input
n = 1
Output
5
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod = 10 ** 9 + 7
dp = [1] * 5
for _ in range(n - 1):
add = [0] * 5
# from a
add[1] = (add[1] + dp[0]) % mod
# from e
add[0] = (add[0] + dp[1]) % mod
add[2] = (add[2] + dp[1]) % mod
# from i
add[0] = (add[0] + dp[2]) % mod
add[1] = (add[1] + dp[2]) % mod
add[3] = (add[3] + dp[2]) % mod
add[4] = (add[4] + dp[2]) % mod
# from o
add[2] = (add[2] + dp[3]) % mod
add[4] = (add[4] + dp[3]) % mod
# from u
add[0] = (add[0] + dp[4]) % mod
for i in range(5):
dp[i] = add[i] % mod
return sum(dp) % mod
Input
n = 1
Output
5