Count Vowels Permutation: Standard DP

Standard DP problem: https://leetcode.com/problems/count-vowels-permutation/

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

The problem will try to deceive you as much as it can. It starts with the title: "Permutation". So in your mind it is already an N! problem. Then in all the examples, in addition to the real output (the actual count), it shows you all the actual possible permutations. Remember that the problem description is not asking for the actual permutations; rather, it just cares about the number of permutations.

Then come the hints that this is a DP (Dynamic Programming) problem: the constraint (10^4) is large enough to rule out any exponential solution, and the fact that the problem mentions this: "Since the answer may be too large, return it modulo 10^9 + 7." should be another cue that you're dealing with a DP problem. Not to mention that this is a HARD L.C. problem.

As with any DP, the approach should not be thought as divide-n-conquer, nor as typical recursion (base case + induction). Instead, the solution is always by construction. You will be constructing the solutions from x=1 (trivial), then 2, then 3, then N-1, and finally N. What you need to think about is this: if you have all the solutions from 1..N-1, can you build the solution for N? The answer is yes. And in fact, because the solution for N depends only on the solution for N-1, you don't even need extra space. Here is the idea:

1. Keep two arrays (len=5) for the previous solution and the current one
2. Use the rules explained in the problem to find solution N from N-1
3. Start from 1 (trivial)
4. As you find the solution for current, reset previous to current
5. When you reach N, you have the solution

Hence linear time (O(N)) and constant space (O(1)). Beats 90% of all other C# submissions. Cheers, ACC.

public class Solution

{

    public int CountVowelPermutation(int n)

    {

        if (n == 1) return 5;

        long mod = 1000000007L;

        //aeiou corresponds to 01234

        long[] previous = new long[5];

        long[] current = new long[5];

        long sumPrevious = 4;

        for (int j = 0; j < 5; j++) previous[j] = 1;

        for (int i = 2; i <= n; i++)

        {

            //a

            current[0] = previous[1];

            //e

            current[1] = (previous[0] + previous[2]) % mod;

            //i

            current[2] = sumPrevious;

            //o

            current[3] = (previous[2] + previous[4]) % mod;

            //u

            current[4] = previous[0];

            sumPrevious = 0;

            for (int j = 0; j < 5; j++)

            {

                previous[j] = current[j];

                if (j != 2) sumPrevious += previous[j];

            }

            sumPrevious %= mod;

        }

        long result = (current[0] + current[1] + current[2] + current[3] + current[4]) % mod;

        return (int)result;

    }

}