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;
    }
};
  • 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;
        }
    }
    
    ############
    
    class Solution {
        private static final long MOD = (long) 1e9 + 7;
    
        public int countVowelPermutation(int n) {
            long[] dp = new long[5];
            long[] t = new long[5];
            Arrays.fill(dp, 1);
            for (int i = 0; i < n - 1; ++i) {
                t[0] = (dp[1] + dp[2] + dp[4]) % MOD;
                t[1] = (dp[0] + dp[2]) % MOD;
                t[2] = (dp[1] + dp[3]) % MOD;
                t[3] = dp[2];
                t[4] = (dp[2] + dp[3]) % MOD;
                System.arraycopy(t, 0, dp, 0, 5);
            }
            long ans = 0;
            for (int i = 0; i < 5; ++i) {
                ans = (ans + dp[i]) % MOD;
            }
            return (int) ans;
        }
    }
    
  • // 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
    
  • func countVowelPermutation(n int) int {
    	const mod int = 1e9 + 7
    	dp := [5]int{1, 1, 1, 1, 1}
    	for i := 0; i < n-1; i++ {
    		dp = [5]int{
    			(dp[1] + dp[2] + dp[4]) % mod,
    			(dp[0] + dp[2]) % mod,
    			(dp[1] + dp[3]) % mod,
    			dp[2],
    			(dp[2] + dp[3]) % mod,
    		}
    	}
    	ans := 0
    	for _, v := range dp {
    		ans = (ans + v) % mod
    	}
    	return ans
    }
    
  • /**
     * @param {number} n
     * @return {number}
     */
    var countVowelPermutation = function (n) {
        const mod = 1000000007;
        const dp = new Array(5).fill(1);
        const t = new Array(5).fill(0);
        for (let i = 0; i < n - 1; ++i) {
            t[0] = (dp[1] + dp[2] + dp[4]) % mod;
            t[1] = (dp[0] + dp[2]) % mod;
            t[2] = (dp[1] + dp[3]) % mod;
            t[3] = dp[2];
            t[4] = (dp[2] + dp[3]) % mod;
            dp.splice(0, 5, ...t);
        }
        let ans = 0;
        for (let i = 0; i < 5; ++i) {
            ans = (ans + dp[i]) % mod;
        }
        return ans;
    };
    
    

All Problems

All Solutions