950. Vowel Follow Rules
A word game forms strings of length n using only the vowels a, e, i, o, u (letters may repeat across the string, but each neighbouring pair must obey a rule). The rules say which vowel may come directly after another: after a only e or i; after e only a or o; after i only a, e or u; after o only i; after u only a or o.
Return how many strings of length n obey every rule, modulo 1_000_000_007 (10^9 + 7).
Example 1
- Input:
- n = 2
- Output:
- 10
- Explanation:
Counting the allowed neighbouring pairs gives a:2 + e:2 + i:3 + o:1 + u:2 = 10 strings of length 2.
Example 2
- Input:
- n = 3
- Output:
- 20
- Explanation:
Extending each of the 10 pairs by every allowed next vowel gives 20 strings of length 3.
Constraints
- 1 ≤ n ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)