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^4This 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.
Java
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.
JavaScript
Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.
| 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. |
Count Vowels Permutation - Dynamic Programming - Leetcode 1220 - Python • NeetCode • 44,927 views views
Watch 9 more video solutions →Practice Count Vowels Permutation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor