Count Vowels Permutation (LeetCode 1220) Solution

The problem

Count the strings of length n built from the vowels a, e, i, o, u that follow these 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.

Return the count modulo 10⁹ + 7.

Input:  n = 2
Output: 10

The valid pairs are ae, ea, ei, ia, ie, io, iu, oi, ou, ua: ten of them.

How to think about it

Start with brute force. Generate every string of length n and check the rules. That’s 5ⁿ strings; even with pruning, the number of valid strings grows exponentially. n goes up to 20,000.

The key insight: the only thing that matters about a string is its last vowel. Whether you can add a character depends only on the character before it. So group strings by their last vowel and keep five counts: how many valid strings of the current length end in a, e, i, o, u.

Flip the rules around to roll forward. To count strings ending in a at the next length, ask “which vowels may be followed by a?”: that’s e, i and u. Doing this for all five:

new a = e + i + u
new e = a + i
new i = e + o
new o = i
new u = i + o

Which pattern is this? Counting DP on a tiny state, a cousin of Climbing Stairs. The tell is “count sequences where each step depends only on the previous one”: the state is the last element.

Approach

Start with length 1: each vowel count is 1.
Repeat n - 1 times: compute all five new counts from the old ones at the same time (tuple assignment), taking each mod 10⁹ + 7.
Return the sum of the five counts, mod 10⁹ + 7.

Solution

def countVowelPermutation(n):
    MOD = 10**9 + 7
    a = e = i = o = u = 1                       # length 1: one string per vowel
    for _ in range(n - 1):
        # new count ending in X = sum of counts of vowels allowed before X
        a, e, i, o, u = (e + i + u) % MOD, (a + i) % MOD, (e + o) % MOD, i % MOD, (i + o) % MOD
    return (a + e + i + o + u) % MOD
# countVowelPermutation(2) -> 10

Dry run

The five counts after each length (no modulus needed this small):

Length	`a`	`e`	`i`	`o`	`u`	Total
1	1	1	1	1	1	5
2	3	2	2	1	2	10
3	6	5	3	2	3	19
4	11	9	7	3	5	35

For n = 2 the answer is 10. Running the code also gives 68 for n = 5, which matches LeetCode’s example.

Complexity

Time: O(n). One constant-time update per extra character.
Space: O(1). Five integers.

Edge cases and pitfalls

n = 1 returns 5: the loop doesn’t run.
Sequential updates are a bug. Writing a = e + i + u and then e = a + i uses the new a. Use tuple assignment or temporaries.
Reading the rules the wrong way round. The rules say what may follow each vowel; the update needs what may precede it. Write both lists down.
Forgetting the modulus works in Python but is wrong in languages with fixed-width integers.
For huge n (say 10¹⁸), raise the 5×5 transition matrix to a power in O(log n). Worth mentioning.

Climbing Stairs (LeetCode 70): the simplest “roll a few counts forward” DP.
Decode Ways (LeetCode 91): counting strings where each step depends on the last one or two characters.
Student Attendance Record II (LeetCode 552): counting DP with a slightly richer state.