Count Sorted Vowel Strings solution and explanation
Google
9 more videos on this problem
Leetcode 1641. Count Sorted Vowel StringsFraz · 10:07 · 18K views
Count Sorted Vowel Strings | Leetcode 1641| Recursion | DP | Day-11Ayushi Sharma · 22:02 · 6K views
Count Sorted Vowel Strings | Live Coding with Explanation | Leetcode - 1641Algorithms Made Easy · 10:15 · 5K views
Dynamic programming + Math: Count sorted vowel strings (LeetCode #1641) [3 solutions]Inside code · 18:03 · 2K views
LeetCode 1641. Count Sorted Vowel Strings - Interview Prep Ep 114Fisher Coder · 14:16 · 2K views
Count Sorted Vowel Strings | Leetcode 1641 O(n) | Live coding sessionCoding Decoded · 11:01 · 2K views
Count Sorted Vowel Strings | Leet code 1641 | Theory explained + Python + JavaSai Anish Malla · 24:48 · 1K views
1641. Count Sorted Vowel Strings (Leetcode Medium)Programming Live with Larry · 9:12 · 1K views
Leetcode #1641 | Count Sorted Vowel Strings | Daily LeetCoding ChallengePRiyanka Singh · 11:14 · 833 views
Leetcode 1641. Count Sorted Vowel Strings | Solution ExplainedPlacement Corner · 8:18 · 707 views
The problem
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.
def countVowelStrings(n: int) -> int:
dp = [[0] * 5 for _ in range(n + 1)]
for j in range(5):
dp[1][j] = 5 - j
for i in range(2, n + 1):
for j in range(4, -1, -1):
dp[i][j] = 0
for k in range(j, 5):
dp[i][j] += dp[i-1][k]
return dp[n][0]public int countVowelStrings(int n) {
int[][] dp = new int[n + 1][5];
for (int j = 0; j < 5; j++) {
dp[1][j] = 5 - j;
}
for (int i = 2; i <= n; i++) {
for (int j = 4; j >= 0; j--) {
dp[i][j] = 0;
for (int k = j; k < 5; k++) {
dp[i][j] += dp[i - 1][k];
}
}
}
return dp[n][0];
}#include <vector>
int countVowelStrings(int n) {
std::vector<std::vector<int>> dp(n+1, std::vector<int>(5, 0));
for (int j = 0; j < 5; ++j) {
dp[1][j] = 5 - j;
}
for (int i = 2; i <= n; ++i) {
for (int j = 4; j >= 0; --j) {
dp[i][j] = 0;
for (int k = j; k < 5; ++k) {
dp[i][j] += dp[i-1][k];
}
}
}
return dp[n][0];
}function countVowelStrings(n) {
let dp = Array.from({length: n + 1}, () => Array(5).fill(0));
for (let j = 0; j < 5; j++) {
dp[1][j] = 5 - j;
}
for (let i = 2; i <= n; i++) {
for (let j = 4; j >= 0; j--) {
dp[i][j] = 0;
for (let k = j; k < 5; k++) {
dp[i][j] += dp[i-1][k];
}
}
}
return dp[n][0];
}#include <stdio.h>
int countVowelStrings(int n) {
int dp[n+1][5];
for (int j = 0; j < 5; j++) {
dp[1][j] = 5 - j;
}
for (int i = 2; i <= n; i++) {
for (int j = 4; j >= 0; j--) {
dp[i][j] = 0;
for (int k = j; k < 5; k++) {
dp[i][j] += dp[i-1][k];
}
}
}
return dp[n][0];
}public int CountVowelStrings(int n) {
int[][] dp = new int[n + 1][];
for (int i = 0; i <= n; i++) {
dp[i] = new int[5];
}
for (int j = 0; j < 5; j++) {
dp[1][j] = 5 - j;
}
for (int i = 2; i <= n; i++) {
for (int j = 4; j >= 0; j--) {
dp[i][j] = 0;
for (int k = j; k < 5; k++) {
dp[i][j] += dp[i-1][k];
}
}
}
return dp[n][0];
}The Python implementation uses list comprehensions to set up dynamic programming tables with iterative replacement based on valid string extension counts.
Time Complexity: O(n * 5 * 5).
Space Complexity: O(n * 5).
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.
import math
def countVowelStrings(n: int) -> int:
return math.comb(n + 4, 4)public int countVowelStrings(int n) {
int count = 1;
for (int i = 1; i <= 4; i++) {
count = count * (n + i) / i;
}
return count;
}#include <iostream>
int comb(int n, int k) {
if (k == 0) return 1;
return (n * comb(n - 1, k - 1)) / k;
}
int countVowelStrings(int n) {
return comb(n + 4, 4);
}function countVowelStrings(n) {
let result = 1;
for (let i = 1; i <= 4; i++) {
result = result * (n + i) / i;
}
return result;
}#include <stdio.h>
int comb(int n, int k) {
if (k == 0) return 1;
return (n * comb(n - 1, k - 1)) / k;
}
int countVowelStrings(int n) {
return comb(n + 4, 4);
}public int CountVowelStrings(int n) {
int result = 1;
for (int i = 1; i <= 4; i++) {
result = result * (n + i) / i;
}
return result;
}Python’s solution leverages its built-in math.comb() function to calculate combinations directly and efficiently.
Time Complexity: O(1), using direct library functionality.
Space Complexity: O(1).
Approach 3: Default Approach
func countVowelStrings(n int) int {
f := make([][5]int, n)
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= n {
return 1
}
if f[i][j] != 0 {
return f[i][j]
}
ans := 0
for k := j; k < 5; k++ {
ans += dfs(i+1, k)
}
f[i][j] = ans
return ans
}
return dfs(0, 0)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * 5 * 5). |
| Combinatorial Mathematics Approach | Time Complexity: O(1), using direct library functionality. |
| Default Approach | – |
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) |
Frequently asked questions
Is Count Sorted Vowel Strings easy or hard?
The problem is labeled Medium because recognizing the combinatorial pattern is not immediately obvious. The dynamic programming solution is straightforward once you understand the ordering constraint, but deriving the O(1) combinatorial formula requires familiarity with stars and bars counting.
How to solve Count Sorted Vowel Strings in O(1)?
Use the combinatorics stars-and-bars formula. The problem reduces to counting non-negative integer solutions to a + e + i + o + u = n. The number of such solutions is C(n + 5 - 1, 5 - 1), which simplifies to C(n+4,4). Computing this binomial coefficient gives the answer instantly.
What is the best approach for Count Sorted Vowel Strings?
The combinatorial mathematics approach is the most optimal. The number of sorted vowel strings of length n equals the number of ways to distribute n characters across five vowels, which is C(n+4,4). This runs in O(1) time and O(1) space. Dynamic programming with O(n) time is also commonly used in interviews to demonstrate the reasoning process.
What data structure is used in Count Sorted Vowel Strings?
The dynamic programming solution typically uses a small array of size five to track counts for strings ending with each vowel. The optimized combinatorial approach does not require any data structures beyond a few integer variables for computing the binomial coefficient.
What is the time complexity of Count Sorted Vowel Strings?
Dynamic programming solves the problem in O(n * 5) time because it updates counts for five vowels for each string length from 1 to n. The combinatorial formula C(n+4,4) reduces the computation to O(1) time with constant space since it directly calculates the number of valid combinations.
Count Sorted Vowel Strings Python or Java solution approach?
Python and Java solutions typically implement either a DP array of size five that accumulates prefix counts across iterations, or compute the binomial coefficient C(n+4,4). The DP approach runs in O(n) time while the combinatorial formula runs in constant time.
Is Count Sorted Vowel Strings asked at Google, Amazon, or Meta?
Count Sorted Vowel Strings is a common combinatorics and dynamic programming interview question. Variants of this problem have appeared in interviews at large tech companies including Amazon and Google, especially when testing counting techniques and DP fundamentals.