1220. Count Vowels Permutation

Description

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.

 

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

 

Constraints:

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const countVowelPermutation = function (n) {
  const MODULO = 10 ** 9 + 7;
  const VOWELS_COUNT = 5;
  const vowelsMap = { a: 0, e: 1, i: 2, o: 3, u: 4 };
  const followedMap = {
    [vowelsMap.a]: [vowelsMap.e, vowelsMap.u, vowelsMap.i],
    [vowelsMap.e]: [vowelsMap.a, vowelsMap.i],
    [vowelsMap.i]: [vowelsMap.e, vowelsMap.o],
    [vowelsMap.o]: [vowelsMap.i],
    [vowelsMap.u]: [vowelsMap.o, vowelsMap.i],
  };
  let dp = Array.from({ length: VOWELS_COUNT }, () => 1);

  for (let index = 2; index <= n; index++) {
    const nextDp = Array.from({ length: VOWELS_COUNT }, () => 0);

    for (let vowels = 0; vowels < VOWELS_COUNT; vowels++) {
      for (const followed of followedMap[vowels]) {
        nextDp[vowels] = (nextDp[vowels] + dp[followed]) % MODULO;
      }
    }
    dp = nextDp;
  }
  return dp.reduce((result, count) => (result + count) % MODULO);
};