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