Chant Syllable Chains

Medium1-D Dynamic Programming

Problem

A choir writes chants as strings of the vowels a, e, i, o, u. To stay singable, each vowel may only be followed by certain vowels:

a → e or i; e → i or o; i → a or u; o → a; u → o or e.

Return how many chants of length n follow these rules, modulo 10^9 + 7.

Example 1

Input:
n = 1
Output:
5

Any single vowel.

Example 2

Input:
n = 2
Output:
9

ae, ai, ei, eo, ia, iu, oa, uo, ue.

Constraints

  • 1 ≤ n ≤ 2·10^4

Hint

Show the first hint

Which information about a chant decides how it can be extended?

Walkthrough

How to approach it

01Clarify before coding

  • Is the first vowel free? Yes, any vowel can start.
  • Are the rules about the next vowel only? Yes, each constraint involves two neighbours.
  • Why modulo? Counts grow roughly by a factor of 1.8 per character.

02Brute force

Generate all 5^n strings and check each adjacent pair.

Cost: O(5^n · n): 5^20 is already about 10^14.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.