Count Sorted Vowel Strings - Solution & Explanation
Problem Statement
Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.
A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.
Example 1:
Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
Example 2:
Input: n = 2 Output: 15 Explanation: The 15 sorted strings that consist of vowels only are ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
Example 3:
Input: n = 33 Output: 66045
Constraints:
1 <= n <= 50
Approach Overview
Problem Overview: Count the number of strings of length n formed using only vowels (a, e, i, o, u) where the characters are sorted in non‑decreasing lexicographic order. For example, "ae" is valid while "ea" is not. The task is essentially counting how many length‑n sequences you can build while preserving vowel order.
Approach 1: Dynamic Programming (O(n * 5) time, O(5) space)
This method builds the answer incrementally using dynamic programming. Define dp[i] as the number of valid strings ending with the i-th vowel. Because the string must stay sorted, a vowel can only follow itself or any vowel before it. Iterate through lengths from 1 to n, updating counts cumulatively: a can only follow a, e can follow a or e, and so on. Each iteration performs prefix-sum style updates across the five vowels.
The key insight is that once the counts for shorter lengths are known, longer lengths can be derived by accumulating allowed predecessors. You can compress the DP into a single array of size five and update it left‑to‑right. This keeps memory constant while maintaining clarity. The final answer is the sum of all five vowel counts after processing length n.
Approach 2: Combinatorial Mathematics (O(1) time, O(1) space)
This problem becomes much simpler when viewed through combinatorics. A sorted vowel string is equivalent to choosing how many times each vowel appears while keeping their order fixed. Instead of constructing the string directly, you distribute n positions among the five vowels.
This is a classic "stars and bars" counting problem from math. You want the number of non‑negative integer solutions to a + e + i + o + u = n. The formula for this distribution is C(n + 5 - 1, 5 - 1), which simplifies to C(n + 4, 4). Computing this binomial coefficient gives the total number of valid sorted vowel strings instantly.
The insight is that sorted order removes permutations. Once you decide how many times each vowel appears, the resulting string is uniquely determined. For example, if a=2, e=1, and others are zero, the string must be "aae". Because the order is fixed, counting combinations directly produces the answer.
Recommended for interviews: Start with the dynamic programming approach. It demonstrates that you understand state transitions and constraints on character ordering. Once the DP pattern is clear, recognizing the combinatorial interpretation (C(n+4,4)) shows deeper insight and often earns bonus points. Most interviewers expect the math shortcut as the optimal solution.
Approach 1: Dynamic Programming Approach
We can use dynamic programming to solve this problem whereby we maintain a table dp[i][j] where i is the length of the string and j is the vowel index from the sorted vowels list [0: 'a', 1: 'e', 2: 'i', 3: 'o', 4: 'u']. Each cell dp[i][j] represents the number of valid strings of length i using the vowels from index j to the end. We initialize the base case for strings of length 1 and fill the table iteratively.
The algorithm initializes a table where dp[i][j] stores numbers of strings of length i from vowel j onward. It calculates each table entry by summing up the possibilities of extending strings of length i-1 with each vowel.
Complexity
Time Complexity: O(n * 5 * 5) = O(n), as we have nested loops running across vowels and length.
Space Complexity: O(n * 5), for storing the table.
Approach 2: Combinatorial Mathematics Approach
Instead of counting strings iteratively, we can view the problem as a mathematical combination problem. Since the string is lexicographically sorted, the placement of 'n' vowels among 'a', 'e', 'i', 'o', 'u' is equivalent to distributing 'n' identical items into 5 distinct groups (vowel buckets). We use the combinatorial formula: C(n + m - 1, m - 1) where 'm' is the number of distinct vowels.
This solution provides a direct combinatory calculation using the formula for combinations. The helper function computes combinations recursively.
Complexity
Time Complexity: O(n), due to the recursive calculation of combination.
Space Complexity: O(n), for the recursive call stack.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * 5 * 5) = O(n), as we have nested loops running across vowels and length. |
| Combinatorial Mathematics Approach | Time Complexity: O(n), due to the recursive calculation of combination. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n * 5) | O(5) | Best for understanding transitions and explaining reasoning in interviews |
| Combinatorial Mathematics (Stars and Bars) | O(1) | O(1) | Optimal solution when you recognize the combination formula C(n+4,4) |
Video Solution
Leetcode 1641. Count Sorted Vowel Strings • Fraz • 18,789 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Sorted Vowel Strings easy or hard?
How to solve Count Sorted Vowel Strings in O(1)?
What is the best approach for Count Sorted Vowel Strings?
What data structure is used in Count Sorted Vowel Strings?
What is the time complexity of Count Sorted Vowel Strings?
Count Sorted Vowel Strings Python or Java solution approach?
Is Count Sorted Vowel Strings asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Count Sorted Vowel Strings with our built-in code editor and test cases.
Practice on FleetCode