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

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;
    }
}

All Problems

All Solutions