Count Vowels Permutation - Leetcode Solution

Problem Statement:

Given an integer n, count how many distinct strings of length n can be formed under the following rules:

1. Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
2. Each vowel 'a' may only be followed by an 'e'.
3. Each vowel 'e' may only be followed by an 'a' or an 'i'.
4. Each vowel 'i' may not be followed by another 'i'.
5. Each vowel 'o' may only be followed by an 'i' or a 'u'.
6. Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Approach:

For this problem, we can use dynamic programming to count the number of distinct strings that can be formed of length n satisfying the given rules.

We define a 2D array dp, where dp[i][j] denotes the number of distinct strings of length i, ending with the vowel j. Here, j can take values from 0 to 4, representing the vowels 'a', 'e', 'i', 'o', 'u' respectively.

To compute dp[i][j], we need to consider all the previous valid vowels k that can be the predecessor of j. The number of valid k's depends on the value of j. We can calculate the sum of all such dp[i-1][k] values for all valid k's and assign it to dp[i][j].

Let's consider the cases for each of the vowels:

1. For 'a', its only valid predecessor is 'e'. So we need to compute dp[i-1][1] for all i.
2. For 'e', its valid predecessors are 'a' and 'i'. So we need to compute dp[i-1][0] and dp[i-1][2] for all i.
3. For 'i', its valid predecessors are 'a', 'e', 'o', and 'u'. But we need to exclude 'i' from the valid ones. So we need to compute dp[i-1][0], dp[i-1][1], dp[i-1][3], and dp[i-1][4] for all i.
4. For 'o', its valid predecessors are 'i' and 'u'. So we need to compute dp[i-1][2] and dp[i-1][4] for all i.
5. For 'u', its only valid predecessor is 'a'. So we need to compute dp[i-1][0] for all i.

The final answer is the sum of all values in the dp[n-1] row, since that row corresponds to all distinct strings of length n satisfying the given rules.

Code:

Time Complexity: O(n) Space Complexity: O(n)

class Solution {
public:
    int countVowelPermutation(int n) {
        long long mod = 1e9 + 7;
        vector<vector<long long>> dp(n, vector<long long>(5, 0));
        
        //Initailizing dp[0] for all vowels
        for(int i=0;i<5;i++){
            dp[0][i] = 1;
        }
        
        for(int i=1;i<n;i++){
            for(int j=0;j<5;j++){
                if(j == 0){
                    dp[i][j] = (dp[i-1][1])%mod;
                }
                else if(j == 1){
                    dp[i][j] = (dp[i-1][0] + dp[i-1][2])%mod;
                }
                else if(j == 2){
                    dp[i][j] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4])%mod;
                }
                else if(j == 3){
                    dp[i][j] = (dp[i-1][2] + dp[i-1][4])%mod;
                }
                else if(j == 4){
                    dp[i][j] = (dp[i-1][0])%mod;
                }
            }
        }
        
        long long ans = 0;
        for(int i=0;i<5;i++){
            ans = (ans + dp[n-1][i])%mod;
        }
        return ans;
    }
};

Hope this helps!

1