Skip to main content

1220. Count Vowels Permutation

hard

Count strings of length n built from vowels following a specific transition graph. A finite-state DP with five rolling counters.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer n, your task is to count how many strings of length n can be formed under the following rules: Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u'). Each vowel 'a' may only be followed by an 'e'. Each vowel 'e' may only be followed by an 'a' or an 'i'. Each vowel 'i' may not be followed by another 'i'. Each vowel 'o' may only be followed by an 'i' or a 'u'. Each vowel 'u' may only be followed by an 'a'. Since the answer may be too large, return it modulo 10^9 + 7.

Constraints

  • 1 <= n <= 2 * 10^4

Examples

Example 1

Input
n = 1
Output
5

Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2

Input
n = 2
Output
10

Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3

Input
n = 5
Output
68

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Reverse the transition rules: who can precede each vowel? Build that adjacency.

Hint 2

Let a, e, i, o, u be counts of strings of length k ending in each vowel. Compute length k+1 counts from previous.

Hint 3

Five rolling scalars; modulo 10^9 + 7.

Solution approach

Reveal approach

Reverse the transition rules: for each vowel, identify which vowels can precede it. From the problem: a follows e, i, or u; e follows a or i; i follows e or o; o follows i; u follows i or o. Maintain five rolling counters (a, e, i, o, u) initialized to 1 each for length 1. For each step from 2 to n compute new values using only the previous-step values: new_a = (e + i + u) mod M; new_e = (a + i) mod M; new_i = (e + o) mod M; new_o = i mod M; new_u = (i + o) mod M. After n - 1 transitions, return (a + e + i + o + u) mod M. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • state-machine
  • matrix-exponentiation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Count Vowels Permutation and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →