1332. Count Vowels Permutation

• Difficulty: Hard

• Topics: Dynamic Programming

• Similar Questions:

Problem:

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

Solutions:

class Solution {
public:
    int countVowelPermutation(int n) {
        if (n == 0) return 1;
        if (n == 1) return 5;

        vector<unordered_map<char, int>> dp(n);

        dp[0] = {
            {'a', 1},
            {'e', 1},
            {'i', 1},
            {'o', 1},
            {'u', 1}
        };

        for (int i = 1; i < n; ++i) {
            unordered_map<char, int> charToCount;
            for (auto& entry : dp[i-1]) {
                char c = entry.first;
                int count = entry.second;
                for (auto& follower : followers[c]) {
                    charToCount[follower] = (charToCount[follower] + count) % MOD;
                }
            }

            dp[i] = charToCount;
        }

        int ret = 0;
        for (auto& entry : dp[n-1]) {
            ret = (ret + entry.second) % MOD;
        }

        return ret;

    }

private:
    const int MOD = 1e9 + 7;
    unordered_map<char, vector<char>> followers {
        {'a', {'e'}},
        {'e', {'a', 'i'}},
        {'i', {'a', 'e', 'o', 'u'}},
        {'o', {'i', 'u'}},
        {'u', {'a'}}
    };

};