Count Vowel Permutations

Problem

Count the strings of length n over the vowels a, e, i, o and u where each vowel is followed only by allowed vowels: a may be followed by e; e by a or i; i by a, e, o or u; o by i or u; and u by a.

Run a DP over the five ending vowels, applying the allowed transitions n - 1 times, and sum the final counts. Assume n >= 1.

Hint

Each DP state is just the final vowel of the current string.

Test cases

case 1

in: [1]

expected: 5

case 2

in: [2]

expected: 10

case 3

in: [3]

expected: 19

case 4

in: [5]

expected: 68

case 5

in: [10]

expected: 1739

Starter codePython

def count_vowel_permutations(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor