1220. Count Vowels Permutation

Problem

Tags: Dynamic Programming

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

Code

CPP

// 1220. Count Vowels Permutation (1/16/53479)
// Runtime: 64 ms (45.36%) Memory: 27.28 MB (21.80%) 

class Solution {
public:
  int countVowelPermutation(int n) {
    constexpr int kMod = 1e9 + 7;
    vector<vector<long>> dp(n + 1, vector<long>(5));
    fill(begin(dp[1]), end(dp[1]), 1);
    // 0: a, 1: e, 2: i, 3: o, 4: u
    for (int i = 2; i <= n; ++i) {
      dp[i][1] += dp[i - 1][0]; // a -> e
      
      dp[i][0] += dp[i - 1][1]; // e -> a
      dp[i][2] += dp[i - 1][1]; // e -> i
      
      for (int j = 0; j < 5; ++j) {
        if (j == 2) continue;
        dp[i][j] += dp[i - 1][2]; // i -> *
      }
      
      dp[i][2] += dp[i - 1][3]; // o -> i
      dp[i][4] += dp[i - 1][3]; // o -> u
      
      dp[i][0] += dp[i - 1][4]; // u -> a
      
      for (int j = 0; j < 5; ++j)
        dp[i][j] %= kMod;
    }
    return accumulate(begin(dp[n]), end(dp[n]), 0L) % kMod;
  }
};