Watch 10 video solutions for Count Vowels Permutation, a hard level problem involving Dynamic Programming. This walkthrough by NeetCode has 47,408 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer n, your task is to count how many strings of length n can be formed under the following rules:
'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'.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^4Problem Overview: You need to count how many strings of length n can be formed using the vowels a, e, i, o, u, while following strict transition rules between characters. Each vowel can only be followed by certain other vowels. The task is to compute the number of valid permutations modulo 1e9 + 7.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
Model the problem using dynamic programming. Define dp[i][v] as the number of valid strings of length i ending with vowel v. Initialize the first position with 1 for every vowel since any vowel can start a string. For each next length, update counts based on the allowed transitions: for example a can follow e, i, or u, while e can follow a or i. Iterate from length 2 to n, applying these transitions and storing results in the DP table. The final answer is the sum of counts for all vowels at length n. This approach clearly represents the recurrence but stores the full DP table.
Approach 2: Dynamic Programming with State Tracking (O(n) time, O(1) space)
You do not actually need the entire DP table. Each step depends only on the counts from the previous step. Track five variables representing strings ending with a, e, i, o, and u. For every iteration, compute the next counts using the transition rules, then overwrite the previous state. For example the next a count equals the sum of previous e, i, and u. This effectively treats the transitions as a small state machine. The algorithm runs in linear time while using constant memory, which is typical for optimized dynamic programming problems with fixed states. The idea is closely related to state compression techniques used in graph-like transition systems.
Recommended for interviews: Interviewers expect the optimized dynamic programming approach with state tracking. Starting with the DP table demonstrates that you understand the recurrence relation and transitions. Compressing the table into five running variables shows stronger problem-solving ability and awareness of space optimization patterns common in dynamic programming problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (DP Table) | O(n) | O(n) | Useful for understanding the recurrence and visualizing transitions between vowels. |
| Dynamic Programming with State Tracking | O(n) | O(1) | Best for interviews and production code when memory optimization matters. |