LeetCode 1220 - Count Vowels Permutation

LeetCode Problem 1220

Difficulty: 🔴 Hard
Topics: Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many valid strings of length n can be formed using only the five lowercase vowels:

'a'
'e'
'i'
'o'
'u'

However, the strings are not arbitrary. Each vowel has strict rules about which vowels may appear immediately after it.

The transition rules are:

'a' can only be followed by 'e'
'e' can only be followed by 'a' or 'i'
'i' can be followed by anything except 'i'
'o' can only be followed by 'i' or 'u'
'u' can only be followed by 'a'

We must compute the total number of valid strings of length n, and because the result can become extremely large, we return the answer modulo 10^9 + 7.

The input consists of a single integer n, representing the desired string length. The output is a single integer representing the count of all valid vowel permutations of that length.

The constraint 1 <= n <= 2 * 10^4 is extremely important. A brute force solution that generates every possible string is completely infeasible because the number of combinations grows exponentially. Even 5^20 is already enormous, and 5^(20000) is astronomically impossible to enumerate.

This tells us immediately that we need a dynamic programming solution where we reuse previously computed results instead of recomputing overlapping subproblems.

Several edge cases are important:

n = 1 is the smallest possible input. Every vowel alone is valid, so the answer should be 5.
Large values of n require efficient time complexity and careful modulo handling.
The transition rules are directional. For example, 'a' -> 'e' is allowed, but 'e' -> 'a' is a separate rule that must be handled independently.
Since 'i' can transition to four different vowels, it contributes heavily to state growth and is easy to implement incorrectly.

Approaches

Brute Force Approach

A brute force solution would recursively generate every possible string of length n.

At each position, we would try every vowel that is allowed according to the transition rules. Once the string reaches length n, we count it as one valid permutation.

This approach is correct because it explicitly explores every valid possibility. However, it is far too slow because the number of possible recursive paths grows exponentially.

Even with pruning based on transition rules, the branching factor remains large enough that the total runtime becomes impractical for n = 20000.

Key Insight for the Optimal Solution

The critical observation is that the next character only depends on the current character.

This means we do not need to store entire strings. Instead, we only need to know:

how many valid strings currently end in 'a'
how many end in 'e'
how many end in 'i'
how many end in 'o'
how many end in 'u'

This is a classic dynamic programming pattern.

For every string length, we compute the number of ways to end with each vowel using the counts from the previous length.

For example:

A string ending in 'a' could only have come from 'e', 'i', or 'u'
A string ending in 'e' could only have come from 'a' or 'i'

By repeatedly updating these five counts, we can build the answer iteratively in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(n)	Recursively generates all valid strings
Optimal Dynamic Programming	O(n)	O(1)	Tracks only counts for each ending vowel

Algorithm Walkthrough

Initialize five variables representing the number of valid strings ending in each vowel.

For length 1, every vowel is valid by itself:

a = 1
e = 1
i = 1
o = 1
u = 1

Iterate from length 2 up to length n.

For every new string length, compute the next counts using the transition rules. 3. Compute the number of strings ending in 'a'.

A string can end in 'a' only if the previous character was:

'e'
'i'
'u'

Therefore:

next_a = e + i + u

Compute the number of strings ending in 'e'.

The previous character must have been:

'a'
'i'

Therefore:

next_e = a + i

Compute the number of strings ending in 'i'.

The previous character must have been:

'e'
'o'

Therefore:

next_i = e + o

Compute the number of strings ending in 'o'.

The previous character must have been:

'i'

Therefore:

next_o = i

Compute the number of strings ending in 'u'.

The previous character must have been:

'i'
'o'

Therefore:

next_u = i + o

Apply modulo 10^9 + 7 to every update.

This prevents integer overflow and satisfies the problem requirement. 9. Replace the old counts with the newly computed counts. 10. After finishing all iterations, return the sum of all five vowel counts modulo 10^9 + 7.

Why it works

The algorithm maintains the invariant that each variable stores the number of valid strings of the current length ending in a specific vowel.

Because every valid string of length k can only transition according to the given rules, the recurrence relations correctly count all possibilities without duplication or omission.

Since every update depends only on the previous length, iterating from 1 to n eventually computes the exact number of valid strings of length n.

Python Solution

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10**9 + 7

        a = e = i = o = u = 1

        for _ in range(1, n):
            next_a = (e + i + u) % MOD
            next_e = (a + i) % MOD
            next_i = (e + o) % MOD
            next_o = i % MOD
            next_u = (i + o) % MOD

            a, e, i, o, u = next_a, next_e, next_i, next_o, next_u

        return (a + e + i + o + u) % MOD

The implementation directly follows the dynamic programming recurrence relations.

We first initialize the counts for strings of length 1. Each vowel contributes exactly one valid string.

The loop runs n - 1 times because length 1 is already initialized. During each iteration, we compute the next state values based on the transition rules.

Temporary variables such as next_a and next_e are necessary because all updates must use the previous iteration's values. If we updated variables in place immediately, later calculations would incorrectly use partially updated data.

After computing all new counts, we replace the old values simultaneously using tuple assignment.

Finally, we sum all possible ending vowels because a valid string may end with any vowel.

Go Solution

func countVowelPermutation(n int) int {
    const MOD int = 1000000007

    a, e, i, o, u := 1, 1, 1, 1, 1

    for step := 1; step < n; step++ {
        nextA := (e + i + u) % MOD
        nextE := (a + i) % MOD
        nextI := (e + o) % MOD
        nextO := i % MOD
        nextU := (i + o) % MOD

        a, e, i, o, u = nextA, nextE, nextI, nextO, nextU
    }

    return (a + e + i + o + u) % MOD
}

The Go implementation mirrors the Python logic almost exactly.

One important difference is explicit integer typing. We define MOD as an int constant and use integer arithmetic throughout.

Go does not support Python-style arbitrary precision integers automatically, but because we apply modulo during every iteration, all intermediate values remain within safe bounds.

Tuple assignment in Go allows simultaneous updates of all five vowel counters, similar to Python.

Worked Examples

Example 1

Input: n = 1

Initial state:

Length	a	e	i	o	u
1	1	1	1	1	1

Total:

1 + 1 + 1 + 1 + 1 = 5

Output:

Example 2

Input: n = 2

Initial state:

Length	a	e	i	o	u
1	1	1	1	1	1

Compute next state:

next_a = e + i + u = 1 + 1 + 1 = 3
next_e = a + i = 1 + 1 = 2
next_i = e + o = 1 + 1 = 2
next_o = i = 1
next_u = i + o = 1 + 1 = 2

Updated table:

Length	a	e	i	o	u
2	3	2	2	1	2

Total:

3 + 2 + 2 + 1 + 2 = 10

Output:

Example 3

Input: n = 5

Initial state:

Length	a	e	i	o	u
1	1	1	1	1	1

After length 2:

Length	a	e	i	o	u
2	3	2	2	1	2

After length 3:

a = 2 + 2 + 2 = 6
e = 3 + 2 = 5
i = 2 + 1 = 3
o = 2
u = 2 + 1 = 3

Length	a	e	i	o	u
3	6	5	3	2	3

After length 4:

Length	a	e	i	o	u
4	11	9	7	3	5

After length 5:

Length	a	e	i	o	u
5	21	18	12	7	10

Total:

21 + 18 + 12 + 7 + 10 = 68

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One iteration per string length
Space	O(1)	Only five counters are stored

The algorithm performs a constant amount of work during each iteration of the loop. Since the loop runs n - 1 times, the total runtime is linear in n.

The space usage is constant because we never store arrays proportional to n. Only five integer counters are maintained regardless of input size.

Test Cases

solution = Solution()

assert solution.countVowelPermutation(1) == 5       # smallest input
assert solution.countVowelPermutation(2) == 10      # basic transition test
assert solution.countVowelPermutation(5) == 68      # provided example

assert solution.countVowelPermutation(3) == 19      # verifies multi-step transitions
assert solution.countVowelPermutation(4) == 35      # intermediate DP growth
assert solution.countVowelPermutation(6) == 129     # larger accumulation

assert solution.countVowelPermutation(10) == 1739   # validates longer sequences

# stress test for performance and modulo handling
result = solution.countVowelPermutation(20000)
assert isinstance(result, int)
assert 0 <= result < 10**9 + 7

Test	Why
`n = 1`	Validates smallest possible input
`n = 2`	Checks direct transition rules
`n = 5`	Matches provided example
`n = 3`	Verifies recurrence correctness
`n = 4`	Ensures iterative state updates work
`n = 6`	Tests continued DP accumulation
`n = 10`	Validates correctness for larger values
`n = 20000`	Confirms performance and modulo handling

Edge Cases

One important edge case is n = 1. Many implementations accidentally enter the DP loop immediately and produce incorrect counts because they assume at least one transition occurs. Our implementation initializes the counts for length 1 directly and skips the loop entirely when n = 1, producing the correct answer of 5.

Another important edge case involves large values of n, especially near 20000. The number of valid strings grows extremely quickly, so implementations that do not apply modulo during every iteration may overflow fixed-size integer types. Our solution applies modulo at each update step, ensuring all intermediate values remain bounded.

A subtle edge case comes from the transition rules for 'i'. The problem states that 'i' may not be followed by another 'i', meaning it may transition to four different vowels. This is easy to misinterpret or partially implement. Our recurrence relations carefully encode all allowed predecessors and successors, ensuring every valid transition is counted exactly once.

A final edge case is simultaneous state updates. If we updated a, then used the updated value to compute e, we would corrupt the recurrence relation because some calculations would use old values while others would use new ones. Using temporary variables such as next_a and next_e guarantees every update uses the previous iteration's state consistently.