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

1220 - Count Vowels Permutation

1220. Count Vowels Permutation (Hard)

Solution 1. DP

All Problems

All Solutions

Welcome to Subscribe On Youtube

1220. Count Vowels Permutation (Hard)

Solution 1. DP

All Problems

All Solutions