Skip to main content
Talentd

Count Vowels Permutation - Solution & Explanation

HardDynamic Programming17 min readAsked at: Mathworks
Practice this problem

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

Approach Overview

Problem 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 1: Dynamic Programming

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:

  • 'a' can only follow 'e',
  • 'e' can follow 'a', 'i',
  • 'i' can't follow 'i', but can follow the others,
  • 'o' can follow 'i', 'u',
  • 'u' can follow 'a'.

After processing n steps, the result is the sum of the counts of strings ending with each vowel, modulo 10^9 + 7.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming with State Tracking

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.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.

Try this approach in the editor →

Approach 3: Matrix Exponentiation to Accelerate Recursion

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming

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.

Dynamic Programming with State Tracking

Time Complexity: O(n) for calculations across string length iteratively.
Space Complexity: O(1), utilizing a constant array scale unrelated to n.

Matrix Exponentiation to Accelerate Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (DP Table)O(n)O(n)Useful for understanding the recurrence and visualizing transitions between vowels.
Dynamic Programming with State TrackingO(n)O(1)Best for interviews and production code when memory optimization matters.

Video Solution

Count Vowels Permutation - Dynamic Programming - Leetcode 1220 - Python • NeetCode • 47,969 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Vowels Permutation easy or hard?
Count Vowels Permutation is classified as Hard on LeetCode. The difficulty comes from recognizing the transition rules as a dynamic programming state machine and implementing the recurrence efficiently.
Count Vowels Permutation Python/Java solution
Both Python and Java implementations follow the same DP transition logic. Track counts for each vowel and update them for each position up to n while applying modulo 1e9+7 to prevent overflow.
How to solve Count Vowels Permutation in O(n)?
Track the number of valid strings ending with each vowel. At every step compute the next counts using the transition rules: a comes from e, i, u; e comes from a, i; i comes from e, o; o comes from i; u comes from i, o. Repeat for n iterations and sum the final counts.
What is the best approach for Count Vowels Permutation?
The best approach uses dynamic programming with state tracking. Maintain five counters representing strings ending in a, e, i, o, and u. Update them each step using the allowed transition rules. This runs in O(n) time and O(1) space.
Is Count Vowels Permutation asked at Google/Amazon/Meta?
This problem represents a classic dynamic programming with state transition pattern that appears in interviews at large tech companies such as Google, Amazon, and Meta. Variations of constrained string counting and DP state transitions are common interview topics.
What data structure is used in Count Vowels Permutation?
The solution primarily uses dynamic programming. Implementations typically store counts in either a DP array like dp[n][5] or five integer variables representing the current vowel states.
What is the time complexity of Count Vowels Permutation?
The optimal solution runs in O(n) time because you process each string length once and update five vowel states. Space complexity can be reduced to O(1) by keeping only the previous step’s counts instead of a full DP table.

Ready to solve this problem?

Practice Count Vowels Permutation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Strings Which Can Be Rearranged to Contain Substring