Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1220.html

1220. Count Vowels Permutation (Hard)

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

Related Topics:
Dynamic Programming

Solution 1. DP

Given the rule, the valid combinations are as follows:

a: ae
e: ea ei
i: ia ie io iu
o: oi ou
u: ua

Let dp[i][j] be the count of valid strings of length i ending with letter j where 0 < i <= n, j = 'a', 'e', 'i', 'o', 'u'.

So we have

dp[i]['a'] = dp[i - 1]['e'] + dp[i - 1]['i'] + dp[i - 1]['u']
dp[i]['e'] = dp[i - 1]['a'] + dp[i - 1]['i']
dp[i]['i'] = dp[i - 1]['e'] + dp[i - 1]['o']
dp[i]['o'] = dp[i - 1]['i']
dp[i]['u'] = dp[i - 1]['i'] + dp[i - 1]['o']

dp[1][j] = 1

The answer is Sum{ dp[n][j] | j = 'a', 'e', 'i', 'o', 'u' }.

// OJ: https://leetcode.com/problems/count-vowels-permutation/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int countVowelPermutation(int n) {
        int mod = 1e9 + 7, a = 1, e = 1, i = 1, o = 1, u = 1;
        while (--n) {
            int aa = ((e + i) % mod + u) % mod;
            int ee = (a + i) % mod;
            int ii = (e + o) % mod;
            int oo = i;
            int uu = (i + o) % mod;
            a = aa, e = ee, i = ii, o = oo, u = uu;
        }
        return ((((a + e) % mod + i) % mod + o) % mod + u) % mod;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public int countVowelPermutation(int n) {
          final int MODULO = 1000000007;
          long[][] dp = new long[n][5];
          Arrays.fill(dp[0], 1);
          for (int i = 1; i < n; i++) {
              dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % MODULO;
              dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MODULO;
              dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % MODULO;
              dp[i][3] = dp[i - 1][2];
              dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % MODULO;
          }
          long sum = 0;
          for (int i = 0; i < 5; i++)
              sum += dp[n - 1][i];
          int count = (int) (sum % MODULO);
          return count;
      }
  }
  

• // OJ: https://leetcode.com/problems/count-vowels-permutation/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int countVowelPermutation(int n) {
          int mod = 1e9 + 7, a = 1, e = 1, i = 1, o = 1, u = 1;
          while (--n) {
              int aa = ((e + i) % mod + u) % mod;
              int ee = (a + i) % mod;
              int ii = (e + o) % mod;
              int oo = i;
              int uu = (i + o) % mod;
              a = aa, e = ee, i = ii, o = oo, u = uu;
          }
          return ((((a + e) % mod + i) % mod + o) % mod + u) % mod;
      }
  };
  

• class Solution:
      def countVowelPermutation(self, n: int) -> int:
          dp = (1, 1, 1, 1, 1)
          MOD = 1000000007
          for _ in range(n - 1):
              dp = (
                  (dp[1] + dp[2] + dp[4]) % MOD,
                  (dp[0] + dp[2]) % MOD,
                  (dp[1] + dp[3]) % MOD,
                  dp[2],
                  (dp[2] + dp[3]) % MOD,
              )
          return sum(dp) % MOD
  
  ############
  
  # 1220. Count Vowels Permutation
  # https://leetcode.com/problems/count-vowels-permutation/
  
  class Solution:
      def countVowelPermutation(self, n: int):
          M = 10 ** 9 + 7
          a = e = i = o = u = 1
          
          for _ in range(2, n+1):
              a,e,i,o,u = e, a+i, a+e+o+u, i+u, a
          
          return (a+e+i+o+u) % M
  

All Problems

All Solutions