Count Vowels Permutation: State Machine DP

Given an integer n, count how many strings of length n can be formed from the lowercase vowels (a, e, i, o, u) where each character must follow specific transition rules. The rules are: 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, and u may only be followed by a. Return the count modulo 10^9 + 7.

This is LeetCode 1220: Count Vowels Permutation, and it is one of the cleanest examples of how to turn a set of transition rules into a compact DP solution.

Why this problem matters

Many DP problems hide a state machine behind their constraints. "From state X, you can move to states Y and Z" is a pattern that shows up in problems about string construction, game theory, and sequence counting. Count Vowels Permutation makes the state machine explicit: the five vowels are the states, and the transition rules tell you exactly which edges exist. Once you see the pattern, you can apply the same framework to problems like Knight Dialer (LeetCode 935), Domino and Tromino Tiling (LeetCode 790), and any problem where the next choice depends only on the current state.

The key insight

The transition rules form a directed graph with five nodes. Instead of generating all valid strings (which would be exponential), you track how many strings of length k end at each vowel. To go from length k to length k + 1, you ask: "Which vowels can precede this vowel?" Then you sum up those predecessors' counts to get the new count for this vowel. This is the reverse view of the transition rules, and it turns the problem into five simple additions per step.

The algorithm:

1. Initialize: for length 1, each vowel has exactly 1 string.
2. For each length from 2 to n, compute new counts using the transition formulas.
3. Sum all five counts and return the result modulo 10^9 + 7.

The solution

def count_vowel_permutation(n: int) -> int:
    MOD = 10**9 + 7
    a = e = i = o = u = 1

    for _ in range(n - 1):
        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

Let's walk through what each piece does.

The five variables a, e, i, o, u represent how many valid strings of the current length end with that vowel. They all start at 1 because there is exactly one string of length 1 for each vowel.

The core loop runs n - 1 times (from length 1 to length n). Each iteration applies the transition rules simultaneously using tuple unpacking. The new value of a is e + i + u because the vowels e, i, and u can all transition to a. Similarly, e gets a + i because only a and i can precede e. The tuple unpacking ensures all values are computed from the previous step before any of them are overwritten.

The final answer sums all five counts, representing every valid string of length n regardless of which vowel it ends with.

Visual walkthrough

Let's trace the DP table for n = 3, building up the counts step by step. At each row, the transition rules pull values from the previous row.

Notice how the transition rules compress the entire problem into five additions per step. No matter how large n gets, the work per step stays constant.

Complexity analysis

Time is O(n). You iterate from 1 to n, and each iteration does a fixed number of additions and modulo operations. The number of states (5 vowels) is constant, so each step is O(1).

Space is O(1). You only store five integers for the current counts. There is no need for a 2D table because each step depends only on the immediately previous step.

The building blocks

1. State transition modeling

The key is recognizing that the "which vowel can follow which" rules define a directed graph. To compute "how many strings of length k end at vowel X," you flip the direction: "which vowels can precede X?" Then you sum those predecessors' counts.

a_new = e + i + u
e_new = a + i
i_new = e + o
o_new = i
u_new = i + o

This is the reverse adjacency list of the transition graph. You will see this "reverse the edges for counting" technique in any state machine DP problem.

2. Rolling DP updates

Since each step depends only on the previous step, you do not need to store the full table. You keep five variables and update them in place using simultaneous assignment.

for _ in range(n - 1):
    a, e, i, o, u = (e + i + u) % MOD, (a + i) % MOD, (e + o) % MOD, i % MOD, (i + o) % MOD

This "rolling" technique reduces space from O(n * k) to O(k) where k is the number of states. You see it in Climbing Stairs, House Robber, and any linear DP where only the last row matters.

Edge cases

Before submitting, think through these scenarios:

• n = 1: Each vowel contributes 1. Answer is 5.
• n = 2: Apply transitions once. Answer is 10.
• Large n (up to 20,000): The modulo operation keeps values bounded. Make sure every addition is followed by % MOD to avoid overflow in languages like C++ or Java.
• Single vowel dominance: As n grows, the distribution across vowels becomes uneven because some vowels have more incoming edges. This does not change the algorithm but is good to understand conceptually.

From understanding to recall

You have seen how five transition rules turn into five lines of DP. The logic is minimal and the code fits in a few lines. But writing it correctly under pressure is a different challenge.

The details that trip people up are subtle. Do you sum predecessors or successors? Do you compute all new values before overwriting the old ones? Do you apply modulo at each step or only at the end? These are not conceptual gaps. They are recall gaps, and they appear under time pressure.

Spaced repetition is how you close them. You practice writing the transition formulas, the rolling update loop, and the modulo handling from memory at increasing intervals. After a few rounds, you see "state machine with transition rules" in a problem and the DP template flows out automatically.

Related posts

• Climbing Stairs - Foundational DP problem with state transitions
• Decode Ways - Another DP problem with transition rules between states
• House Robber - DP with constraints on which states can follow which

CodeBricks breaks Count Vowels Permutation into its state transition modeling and rolling DP building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a state machine DP problem shows up in your interview, you do not hesitate. You just write it.