#1220 Count Vowels Permutation - Solution

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

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

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

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

Count Vowels Permutation asks you to count how many strings of length n can be formed using vowels while following specific transition rules between characters. Because each position depends only on the previous character, the problem naturally fits a Dynamic Programming model.

Define DP states representing how many valid strings end with each vowel (a, e, i, o, u) at a given length. Using the allowed transitions, you update the counts for the next position based on the previous one. Since only five vowels exist, the state size stays constant while iterating up to n. To avoid overflow, results are typically taken modulo 1e9+7.

This approach runs in O(n) time with constant memory by tracking only the previous step’s counts. For very large n, the transitions can also be represented as a matrix and solved using matrix exponentiation to reduce time complexity.

Approach	Time Complexity	Space Complexity
Dynamic Programming with vowel states	O(n)	O(1)
Matrix Exponentiation optimization	O(log n)	O(1)

Solutions (4)

Dynamic Programming

This approach uses dynamic programming to build up the solution by storing the number of strings of length n ending with each vowel, based on the rules provided. We use a table where each row corresponds to a length from 1 to n, and each column corresponds to a vowel. The value at each cell (i, j) represents the number of strings of length i that end with the respective vowel j.

We update this table iteratively by considering the transition rules from one vowel to another, ensuring only valid transitions contribute to the count. Finally, we sum up the counts for all vowels at length n to get the result.

Time Complexity: O(n), since we iterate through each position up to n.
Space Complexity: O(1), since we only keep track of the current and next states without additional memory usage.

Python Java

1def count_vowel_permutation(n):
2    MOD = 10**9 + 7
3    # Vowel states initialized
4    dp = [1, 1, 1, 1, 1]  # Represents counts for a, e, i, o, u respectively
5    for _ in range(1, n):
6        dp_next = [0] * 5
7        dp_next[0] = (dp[1]) % MOD  # a can follow e
8        dp_next[1] = (dp[0] + dp[2]) % MOD  # e can follow a, i
9        dp_next[2] = (dp[0] + dp[1] + dp[3] + dp[4]) % MOD  # i can follow a, e, o, u
10        dp_next[3] = (dp[2] + dp[4]) % MOD  # o can follow i, u
11        dp_next[4] = (dp[0]) % MOD  # u can follow a
12        dp = dp_next
13    return sum(dp) % MOD
14
15# Usage: 
16# print(count_vowel_permutation(1))  # Output: 5
17# print(count_vowel_permutation(2))  # Output: 10

Explanation

The Python code uses an array to track the number of paths ending with each vowel. In each iteration, a new array 'dp_next' is computed based on the current state of 'dp'. Each array index corresponds to a vowel, and they are updated according to the transition rules given:

'a' can only follow 'e',
'e' can follow 'a', 'i',
'i' can't follow 'i', but can follow the others,
'o' can follow 'i', 'u',
'u' can follow 'a'.

After processing n steps, the result is the sum of the counts of strings ending with each vowel, modulo 10^9 + 7.

Dynamic Programming with State Tracking

This approach is similar to the previous one but breaks down the state transitions further into distinct functions, or transitions explicitly defined between states (vowels). It effectively uses a dynamic programming table but emphasizes clear rules defining how counts from one step translate to the next.

Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.

C++JavaScript

1#include <iostream>
2#include <vector>
3
4class VowelPermutation {
5public:
    int countVowelPermutation(int n) {
        const int MOD = 1000000007;
        std::vector<long> dp(5, 1); // a, e, i, o, u
        for (int i = 1; i < n; ++i) {
            std::vector<long> dpNext(5);
            dpNext[0] = (dp[1] + dp[2] + dp[4]) % MOD; // a follows e, i, u
            dpNext[1] = (dp[0] + dp[2]) % MOD;        // e follows a, i
            dpNext[2] = (dp[1] + dp[3]) % MOD;        // i follows e, o
            dpNext[3] = dp[2] % MOD;                  // o follows i
            dpNext[4] = (dp[2] + dp[3]) % MOD;        // u follows i, o
            dp = dpNext;
        }
        long sum = 0;
        for (long x : dp) sum = (sum + x) % MOD;
        return sum;
    }
};

int main() {
    VowelPermutation vp;
    std::cout << vp.countVowelPermutation(1) << std::endl; // Output: 5
    std::cout << vp.countVowelPermutation(2) << std::endl; // Output: 10
    return 0;
}