Count Vowels Permutation

Problem Statement

Given an integer n, the problem asks to determine the number of strings of length n that can be constructed using the vowels: 'a', 'e', 'i', 'o', 'u'. Each vowel has specific rules concerning which vowels can follow it in the string:

• 'a' can only be followed by 'e'.
• 'e' can be followed by 'a' or 'i'.
• 'i' can be followed by any vowel except 'i' itself.
• 'o' can be followed by 'i' or 'u'.
• 'u' can be followed by 'a'.

These rules significantly influence the string construction, making it a constrained combinatorial problem. Given the potential size of the output, it must be returned modulo (10^9 + 7) to prevent overflow issues.

Examples

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

Approach and Intuition

To solve the problem of counting the number of valid strings of length n under the given constraints, we need to think in terms of dynamic programming or combinatorial counting with transition rules based on the established sequence-building restrictions:

1. Initialization: Consider the base scenario when n is 1. Here, each of the vowels 'a', 'e', 'i', 'o', 'u' are valid strings in themselves. Therefore, there are 5 possible strings when n equals 1.

2. Recursive Relation Development: For lengths greater than one, determine the number of ways to form sequences of length n based on sequences of length n-1. Develop a relationship based on permitted transitions:

   • If a string of length n ends in 'a', the string of length n-1 could have ended in 'e' or 'u' based on the rules specified.
   • If it ends in 'e', it could have been 'a' or 'i' previously.
   • For an ending 'i', the preceding character could have been 'e', 'o', or 'u'.
   • Similarly, develop transition counts for strings ending in 'o' and 'u'.

3. Dynamic Programming Table Construction: Use dp (a dynamic programming table) where dp[i][v] represents the number of valid strings of length i that end with vowel v. Intuitively fill this table based on n and using transitions defined:

   • The recursive relations will allow you to populate dp table row by row for each vowel ending.

4. Result Calculation: Finally, for the desired length n, the result would be the sum of all strings ending in any vowel calculated from the dp table, i.e., sum of all dp[n][vowel]. Return this result modulo (10^9 + 7).

This approach ensures that each position in the string is built upon the valid preceding configurations, satisfying the transition constraints optimally.

Solutions

class Solution {
    private long[][] dp;
    private final int MODULO = 1000000007;
    
    public int countVowelPermutation(int length) {
        dp = new long[length][5];
        long sum = 0;
        for (int i = 0; i < 5; i++) {
            sum = (sum + calculatePermutations(length - 1, i)) % MODULO;
        }
        return (int)sum;
    }
    
    private long calculatePermutations(int len, int vowelIndex) {
        if (dp[len][vowelIndex] != 0) return dp[len][vowelIndex];
        if (len == 0) {
            dp[len][vowelIndex] = 1;
        } else {
            if (vowelIndex == 0) {
                dp[len][vowelIndex] = (calculatePermutations(len - 1, 1) + calculatePermutations(len - 1, 2) + calculatePermutations(len - 1, 4)) % MODULO;
            } else if (vowelIndex == 1) {
                dp[len][vowelIndex] = (calculatePermutations(len - 1, 0) + calculatePermutations(len - 1, 2)) % MODULO;
            } else if (vowelIndex == 2) {
                dp[len][vowelIndex] = (calculatePermutations(len - 1, 1) + calculatePermutations(len - 1, 3)) % MODULO;
            } else if (vowelIndex == 3) {
                dp[len][vowelIndex] = calculatePermutations(len - 1, 2);
            } else if (vowelIndex == 4) {
                dp[len][vowelIndex] = (calculatePermutations(len - 1, 2) + calculatePermutations(len - 1, 3)) % MODULO;
            }
        }
        return dp[len][vowelIndex];
    }
}