Count Vowels Permutation
We can solve this problem by using Dynamic Programming. Let’s define a 2D array dp
, where dp[i][j]
represents the count of vowel permutations of length i
ending with the vowel at index j
.
We iterate through the string of length n
and update the counts according to the given rules.
Here’s the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def countVowelPermutation(self, n: int) -> int:
MOD = 10**9 + 7
# dp[i][j] represents the count of vowel permutations of length i ending with the vowel at index j
dp = [[0] * 5 for _ in range(n + 1)]
# Base case: There is one permutation for each vowel of length 1
for j in range(5):
dp[1][j] = 1
# Iterate through the string of length n
for i in range(2, n + 1):
# Update counts according to the rules
dp[i][0] = dp[i - 1][1] # 'a' follows 'e'
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD # 'e' follows 'a' or 'i'
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4]) % MOD # 'i' follows all except 'i'
dp[i][3] = (dp[i - 1][2] + dp[i - 1][4]) % MOD # 'o' follows 'i' or 'u'
dp[i][4] = dp[i - 1][0] # 'u' follows 'a'
# Sum all the counts of vowel permutations of length n
return sum(dp[n]) % MOD
|
The MOD
constant is used to keep the result within the required bounds.
The time complexity of this code is (O(n)), and the space complexity is also (O(n)).