MANG Problem #46: Count Vowels Permutation (Hard)

1. Problem Statement

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').
'a' may only be followed by an 'e'.
'e' may only be followed by an 'a' or an 'i'.
'i' may not be followed by another 'i'.
'o' may only be followed by an 'i' or a 'u'.
'u' may only be followed by an 'a'.

Return the answer modulo $10^9 + 7$.

2. Approach: DP / State Machine

The rules define a Directed Graph or a State Machine. For example, to form a valid string ending in 'a' of length N, we must look at valid strings of length N-1. What letters can precede 'a'? Based on the rules, only 'e', 'i', and 'u' can be followed by 'a'.

So, count(a, N) = count(e, N-1) + count(i, N-1) + count(u, N-1).

We can maintain 5 variables representing the number of strings of length N ending in each vowel.

3. Java Implementation

public int countVowelPermutation(int n) {
    long MOD = 1_000_000_007;
    
    // dp[vowel] tracks the number of strings of the current length ending with that vowel
    long a = 1, e = 1, i = 1, o = 1, u = 1;
    
    for (int length = 2; length <= n; length++) {
        // Calculate new counts based on transition rules
        long next_a = (e + i + u) % MOD;
        long next_e = (a + i) % MOD;
        long next_i = (e + o) % MOD;
        long next_o = i % MOD;
        long next_u = (i + o) % MOD;
        
        // Update states
        a = next_a;
        e = next_e;
        i = next_i;
        o = next_o;
        u = next_u;
    }
    
    return (int) ((a + e + i + o + u) % MOD);
}

4. 5-Minute "Video-Style" Walkthrough

The Rule Inversion: The problem states what a vowel can be followed by. To use bottom-up DP, we must invert this: "What can this vowel be preceded by?"
- 'a' follows 'e', 'i', 'u'.
- 'e' follows 'a', 'i'.
- 'i' follows 'e', 'o'.
- 'o' follows 'i'.
- 'u' follows 'i', 'o'.
Space Optimization: We only ever need the counts from length N-1 to calculate length N. Therefore, we don't need an N x 5 DP matrix. We only need 5 variables! This reduces space from $O(N)$ to $O(1)$.
The Modulo Trap: Never wait until the final addition to apply the modulo. Values will quickly overflow long if you don't apply % MOD at every single addition step.

5. Interview Discussion

Interviewer: "What is the time and space complexity?"
You: "Time complexity is $O(N)$ because we iterate $N$ times. Space complexity is $O(1)$ because we only maintain 5 variables regardless of $N$."
Interviewer: "Can this be solved in O(log N) time?"
You: "Yes, this is an advanced math trick. Because the transitions are constant linear combinations, we can represent them as an Adjacency Matrix and use Matrix Exponentiation. Computing $M^N$ takes $O(\log N)$ time."