MANG Problem #46: Count Vowels Permutation (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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."

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #46: Count Vowels Permutation (Hard)', I focused on reducing the time complexity by leveraging a Dynamic Programming state transition. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by using in-place modifications. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

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'.