Problem statement

Given an integer n, count the strings of length n over the vowels a, e, i, o, u that obey every rule:

• 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^9 + 7.

Example 1

Input: n = 1
Output: 5
Explanation: All five single vowels qualify.

Example 2

Input: n = 2
Output: 10

Example 3

Input: n = 5
Output: 68

Constraints

• 1 <= n <= 2000

Hints for Count Vowels Permutation

1. Hint 1

   Let dp[v] be the number of valid strings of the current length that end in vowel v.

2. Hint 2

   Extending by one character redistributes those counts along the allowed transitions.

3. Hint 3

   The i rule is easiest read backwards: i may be preceded by anything except i itself.

How to solve Count Vowels Permutation

Keep the count of valid strings ending in each vowel; extending by one character redistributes counts along the allowed transitions read backwards (what may precede each vowel).

Approach

1. Start every vowel at 1 (length 1).
2. Repeat n - 1 times: a' = e + i + u, e' = a + i, i' = e + o, o' = i, u' = i + o, all modulo 10⁹+7.
3. Return the sum.

Why it works

The rules define a directed graph on the five vowels; the number of length-n walks ending at v is the sum over its in-neighbours of length-n-1 walks, which is exactly the recurrence.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Derive the backward adjacency carefully: a can be preceded by e, i, u because those are the vowels allowed to be followed by a.

Reference solution

Python

def countVowelPermutation(n: int) -> int:
    MOD = 1000000007
    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

Java

public static int countVowelPermutation(int n) {
    final long MOD = 1000000007L;
    long a = 1, e = 1, i = 1, o = 1, u = 1;
    for (int step = 1; step < n; step++) {
        long na = (e + i + u) % MOD;
        long ne = (a + i) % MOD;
        long ni = (e + o) % MOD;
        long no = i % MOD;
        long nu = (i + o) % MOD;
        a = na; e = ne; i = ni; o = no; u = nu;
    }
    return (int) ((a + e + i + o + u) % MOD);
}

C++

int countVowelPermutation(int n) {
    const long long MOD = 1000000007LL;
    long long a = 1, e = 1, i = 1, o = 1, u = 1;
    for (int step = 1; step < n; step++) {
        long long na = (e + i + u) % MOD;
        long long ne = (a + i) % MOD;
        long long ni = (e + o) % MOD;
        long long no = i % MOD;
        long long nu = (i + o) % MOD;
        a = na; e = ne; i = ni; o = no; u = nu;
    }
    return (int) ((a + e + i + o + u) % MOD);
}

JavaScript

var countVowelPermutation = function(n) {
    const MOD = 1000000007;
    let a = 1, e = 1, i = 1, o = 1, u = 1;
    for (let step = 1; step < n; step++) {
        const na = (e + i + u) % MOD;
        const ne = (a + i) % MOD;
        const ni = (e + o) % MOD;
        const no = i % MOD;
        const nu = (i + o) % MOD;
        a = na;
        e = ne;
        i = ni;
        o = no;
        u = nu;
    }
    return (a + e + i + o + u) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Maximum Sum BST in Binary Tree Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• Time Taken to Mark All Nodes Hard