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.
This approach uses dynamic programming to build up the solution by storing the number of strings of length n ending with each vowel, based on the rules provided. We use a table where each row corresponds to a length from 1 to n, and each column corresponds to a vowel. The value at each cell (i, j) represents the number of strings of length i that end with the respective vowel j.
We update this table iteratively by considering the transition rules from one vowel to another, ensuring only valid transitions contribute to the count. Finally, we sum up the counts for all vowels at length n to get the result.
The Python code uses an array to track the number of paths ending with each vowel. In each iteration, a new array 'dp_next' is computed based on the current state of 'dp'. Each array index corresponds to a vowel, and they are updated according to the transition rules given:
After processing n steps, the result is the sum of the counts of strings ending with each vowel, modulo 10^9 + 7.
Python
Java
C++
Go
TypeScript
JavaScript
Time Complexity: O(n), since we iterate through each position up to n.
Space Complexity: O(1), since we only keep track of the current and next states without additional memory usage.
This approach is similar to the previous one but breaks down the state transitions further into distinct functions, or transitions explicitly defined between states (vowels). It effectively uses a dynamic programming table but emphasizes clear rules defining how counts from one step translate to the next.
The C++ code offers a slightly more verbose approach, further clarifying transitions between each vowel index state. Functional decomposition is used by specifying transition rules explicitly for each vowel state, showing how dp[i] evolves into dp[next]. This approach emphasizes clarity of state changes across each step n.
C++
JavaScript
Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.
The time complexity is O(C^3 times log n), and the space complexity is O(C^2). Here, C is the number of vowels. In this problem, C=5.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n), since we iterate through each position up to n. |
| Dynamic Programming with State Tracking | Time Complexity: O(n) for calculations across string length iteratively. |
| Matrix Exponentiation to Accelerate Recursion | — |
| 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. |
Count Vowels Permutation - Dynamic Programming - Leetcode 1220 - Python • NeetCode • 47,408 views views
Watch 9 more video solutions →Practice Count Vowels Permutation with our built-in code editor and test cases.
Practice on FleetCode