#1220

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Vowels Permutation

Count Vowels Permutation requires computing the number of valid vowel strings of length n using state transition dynamic programming efficiently.

dynamic programming

Problem Statement

Given an integer n, determine how many strings of length n can be constructed using vowels 'a', 'e', 'i', 'o', 'u' following specific transition rules: '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'.

Because the number of valid strings grows rapidly with n, return the count modulo 10^9 + 7. For example, with n = 1, the result is 5 since each vowel forms a valid string. With n = 2, the total valid strings are 10 following the transition rules.

Examples

Example 1

Input: n = 1

Output: 5

All possible strings are: "a", "e", "i" , "o" and "u".

Example 2

Input: n = 2

Output: 10

All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3

Input: n = 5

Output: 68

Example details omitted.

Constraints

1 <= n <= 2 * 10^4

Solution Approach

Dynamic Programming Table

Use a DP array where dp[i][v] stores the number of strings of length i ending with vowel v. Initialize the first row with 1 for each vowel. Iterate from 2 to n, updating each dp[i][v] according to the allowed transitions. Finally, sum dp[n] to get the answer modulo 10^9 + 7.

Space Optimization

Instead of a full n x 5 DP table, track only the counts for the previous step in a single array of size 5. Update counts in place for each new length, reducing space from O(n*5) to O(5), while maintaining the state transition logic.

Modulo Handling

At each DP update, apply modulo 10^9 + 7 to prevent integer overflow. This is crucial for large n up to 2*10^4, ensuring that intermediate sums never exceed the integer limits while preserving correctness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each step updates 5 states. Space complexity is O(5) with optimized DP, or O(n*5) with a full DP table. Both are efficient for n up to 20,000.

What Interviewers Usually Probe

Focus on optimizing space while maintaining correct vowel transitions.
Check for off-by-one errors when applying state transitions.
Be ready to explain why modulo 10^9 + 7 is required for large n.

Common Pitfalls or Variants

Common pitfalls

Incorrectly allowing forbidden transitions like 'i' followed by 'i'.
Forgetting to apply modulo after each sum operation, leading to overflow.
Using a full DP table without space optimization for large n, wasting memory.

Follow-up variants

Count consonant permutations with custom transition rules.
Allow cyclic transitions and compute permutations with modified DP.
Extend to strings including both vowels and consonants under state rules.

FAQ

What is the main pattern in Count Vowels Permutation?

The core pattern is state transition dynamic programming, where each vowel can follow only specific previous vowels.

Why do we use modulo 10^9 + 7 in this problem?

The count grows exponentially with n, so modulo prevents integer overflow and keeps calculations manageable.

Can we optimize space in this problem?

Yes, by storing only the counts for the previous length instead of a full DP table, reducing space to O(5).

What is a common mistake when implementing DP for this problem?

Allowing forbidden transitions, such as 'i' followed by 'i', or forgetting modulo at each step.

How do initial values affect the DP approach?

Each vowel at length 1 starts with a count of 1, which seeds the DP iteration correctly.

terminal

Solution

Solution 1: Dynamic Programming

Based on the problem description, we can list the possible subsequent vowels for each vowel:

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [1] * 5
        mod = 10**9 + 7
        for _ in range(n - 1):
            g = [0] * 5
            g[0] = (f[1] + f[2] + f[4]) % mod
            g[1] = (f[0] + f[2]) % mod
            g[2] = (f[1] + f[3]) % mod
            g[3] = f[2]
            g[4] = (f[2] + f[3]) % mod
            f = g
        return sum(f) % mod

Solution 2: Matrix Exponentiation to Accelerate Recursion

The time complexity is $O(C^3 \times \log n)$, and the space complexity is $O(C^2)$. Here, $C$ is the number of vowels. In this problem, $C=5$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [1] * 5
        mod = 10**9 + 7
        for _ in range(n - 1):
            g = [0] * 5
            g[0] = (f[1] + f[2] + f[4]) % mod
            g[1] = (f[0] + f[2]) % mod
            g[2] = (f[1] + f[3]) % mod
            g[3] = f[2]
            g[4] = (f[2] + f[3]) % mod
            f = g
        return sum(f) % mod

Continue Practicing

#1218 longest arithmetic subsequence of given difference #1223 dice roll simulation #1227 airplane seat assignment probability