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)).