Code Implementation

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        # a, e, i, o, u
        dp = [1] * 5
        for _ in range(1, n):
            a = (dp[1] + dp[2] + dp[4]) % MOD
            e = (dp[0] + dp[2]) % MOD
            i = (dp[1] + dp[3]) % MOD
            o = dp[2] % MOD
            u = (dp[2] + dp[3]) % MOD
            dp = [a, e, i, o, u]
        return sum(dp) % MOD
      

class Solution {
public:
    int countVowelPermutation(int n) {
        const int MOD = 1e9 + 7;
        long a = 1, e = 1, i = 1, o = 1, u = 1;
        for (int k = 1; k < n; ++k) {
            long na = (e + i + u) % MOD;
            long ne = (a + i) % MOD;
            long ni = (e + o) % MOD;
            long no = i % MOD;
            long nu = (i + o) % MOD;
            a = na; e = ne; i = ni; o = no; u = nu;
        }
        return (a + e + i + o + u) % MOD;
    }
};
      

class Solution {
    public int countVowelPermutation(int n) {
        int MOD = 1000000007;
        long a = 1, e = 1, i = 1, o = 1, u = 1;
        for (int k = 1; k < n; ++k) {
            long na = (e + i + u) % MOD;
            long ne = (a + i) % MOD;
            long ni = (e + o) % MOD;
            long no = i % MOD;
            long nu = (i + o) % MOD;
            a = na;
            e = ne;
            i = ni;
            o = no;
            u = nu;
        }
        return (int)((a + e + i + o + u) % MOD);
    }
}
      

var countVowelPermutation = function(n) {
    const MOD = 1e9 + 7;
    let a = 1, e = 1, i = 1, o = 1, u = 1;
    for (let k = 1; k < n; ++k) {
        let na = (e + i + u) % MOD;
        let ne = (a + i) % MOD;
        let ni = (e + o) % MOD;
        let no = i % MOD;
        let nu = (i + o) % MOD;
        a = na; e = ne; i = ni; o = no; u = nu;
    }
    return (a + e + i + o + u) % MOD;
};
      

Problem Description

Given an integer n, you are asked to return the number of strings of length n that can be formed using only the vowels 'a', 'e', 'i', 'o', and 'u' under the following rules:

• Each character of the string must be a vowel.
• Certain vowels can only follow specific other vowels:
  • 'a' may only be followed by 'e'.
  • 'e' may only be followed by 'a' or 'i'.
  • 'i' may not be followed by another 'i'.
  • 'o' may only be followed by 'i' or 'u'.
  • 'u' may only be followed by 'a'.
• Return your answer modulo 10^9 + 7.

The task is to count all possible valid strings of length n that can be constructed under these constraints.

Thought Process

At first glance, this problem appears to involve generating all possible vowel strings of length n and counting those that obey the transition rules. However, as n increases, the number of possible strings grows exponentially, making brute-force enumeration infeasible.

To optimize, we realize that the restrictions on which vowel can follow which form a set of transitions. This suggests a dynamic programming approach, where we keep track of the number of valid strings ending with each vowel at each position in the string.

Instead of tracking every possible string, we only need to track counts for each vowel at each length, updating these counts based on the allowed transitions.

Solution Approach

We use dynamic programming to keep track of how many strings of a given length end with each vowel. The idea is to build up the solution one character at a time, using the transition rules.

1. State Definition: Let dp[vowel] represent the number of ways to form a string of the current length ending with vowel.
2. Initialization: For length 1, each vowel can appear once. So, dp = [1, 1, 1, 1, 1] for 'a', 'e', 'i', 'o', and 'u' respectively.
3. Transitions: For each subsequent character, update the counts based on which vowels can follow which:
   • 'a' can follow 'e', 'i', 'u'
   • 'e' can follow 'a', 'i'
   • 'i' can follow 'e', 'o'
   • 'o' can follow 'i'
   • 'u' can follow 'i', 'o'
4. Iteration: For each position from 2 to n, update the counts for each vowel using the previous counts and the above transitions.
5. Result: The total number of valid strings is the sum of the counts for all vowels at length n.
6. Modulo Operation: Since the result can be very large, take the answer modulo 10^9 + 7 at each step to avoid overflow.

This approach ensures we only ever store five numbers at a time, making it both time and space efficient.

Example Walkthrough

Let's walk through the case where n = 2.

• Initialization (length 1):
  • a = 1, e = 1, i = 1, o = 1, u = 1
• Build for length 2:
  • New a: can be after e, i, u → a = e + i + u = 1 + 1 + 1 = 3
  • New e: can be after a, i → e = a + i = 1 + 1 = 2
  • New i: can be after e, o → i = e + o = 1 + 1 = 2
  • New o: can be after i → o = i = 1
  • New u: can be after i, o → u = i + o = 1 + 1 = 2
• Total valid strings of length 2: 3 + 2 + 2 + 1 + 2 = 10

So, for n = 2, there are 10 valid vowel permutations.

Time and Space Complexity

• Brute-force Approach:
  • Would generate all possible strings of length n using 5 vowels, i.e., 5^n possibilities.
  • Time complexity: O(5^n)
  • Space complexity: O(n) for recursion stack (if using backtracking)
• Optimized Dynamic Programming Approach:
  • For each of n positions, we do constant (5) work.
  • Time complexity: O(n)
  • Space complexity: O(1) (since we only keep counts for 5 vowels)

The DP approach is exponentially faster and uses minimal space.

Summary

The key insight is to recognize that this problem is about counting, not generating, valid strings. By modeling the allowed transitions with dynamic programming, we avoid the exponential blowup of brute-force methods. The solution is elegant because it leverages the small, fixed set of states (the vowels) and the predictable transitions between them, resulting in a very efficient algorithm.