Count Sorted Vowel Strings

Given an integer n, you need to count how many strings of length n can be formed using only the vowels a, e, i, o, u, where each string is lexicographically sorted. That means every character must be greater than or equal to the one before it.

This is LeetCode 1641: Count Sorted Vowel Strings, and it is a great problem for seeing how a clean DP formulation can lead you straight to a closed-form math solution. The two approaches reinforce each other nicely.

The problem

You are given n, and you need to return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are sorted in non-decreasing order. For example, "ae", "aa", "uu", and "aeiou" are valid for their respective lengths, but "ea" is not because e comes after a.

For n = 1, the answer is 5 (just the five individual vowels). For n = 2, the answer is 15. For n = 33, the answer is 66045. The numbers grow quickly but follow a predictable pattern.

The brute force approach

The most direct approach is to generate all possible strings recursively. At each position, you pick a vowel that is greater than or equal to the previous one. You start from position 0 and branch out:

def count_vowel_strings(n):
    def backtrack(pos, start):
        if pos == n:
            return 1
        total = 0
        for i in range(start, 5):
            total += backtrack(pos + 1, i)
        return total

    return backtrack(0, 0)

This works but is slow. Each position branches up to 5 ways, giving a worst-case time complexity around O(5^n). For n = 50, that is way too many calls. You need a smarter approach.

The key insight

Think about what this recursion is really doing. At each position, you choose a vowel index from start to 4, and then the subproblem is "how many sorted strings of the remaining length can I build starting from that index?" The subproblems overlap heavily. If you call backtrack(3, 2) from two different paths, you are doing the same work twice.

Define dp[i][j] as the number of sorted vowel strings of length i where the first character is vowel j or any vowel after it. The recurrence is:

• Base case: dp[1][j] = 1 for all j (a single vowel is always sorted)
• Transition: dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][4]

That transition is just a suffix sum. Each cell equals the sum of all cells to its right in the previous row, plus itself. The answer for a given n is dp[n][0], the count of sorted strings of length n starting from vowel "a" or later (meaning all vowels are allowed).

Step-by-step walkthrough

Let's trace through the DP table row by row. Each row represents a string length, and each column represents a starting vowel.

Notice the pattern: the "u" column is always 1 (only one sorted string can start with u: all u's). The "a" column holds the answer for that length, since starting from "a" means all vowels are available. And each cell is the suffix sum of the row above.

The code

Here is the DP approach, clean and direct:

def count_vowel_strings(n):
    dp = [1, 1, 1, 1, 1]

    for i in range(1, n):
        for j in range(3, -1, -1):
            dp[j] += dp[j + 1]

    return dp[0]

The trick is that you do not need a full 2D table. Since each row only depends on the previous row, you can update in place. You iterate right to left so that each cell picks up the already-updated values to its right, which gives you the suffix sum behavior.

And here is the math approach using combinations:

from math import comb

def count_vowel_strings(n):
    return comb(n + 4, 4)

That is it. The stars and bars formula C(n + k - 1, k - 1) with k = 5 gives C(n + 4, 4). The DP approach helps you understand why the formula works, and the math approach gives you the most efficient implementation.

Complexity analysis

The building blocks

Suffix sums in DP transitions

The core mechanic here is that each DP cell is the suffix sum of the previous row. This is a common pattern in counting problems where you have ordered choices. Whenever your transition says "sum up all options from index j to the end," you are doing a suffix sum. Recognizing this lets you compute each row in O(k) time instead of O(k^2).

This same idea shows up in problems like Combination Sum IV (LeetCode 377), where you sum over all valid choices at each step, and in problems involving counting paths through grids with constraints.

Stars and bars (combinatorics)

The stars and bars technique counts the number of ways to distribute n identical items into k distinct bins. Here the "items" are positions in the string and the "bins" are the 5 vowels. Since the string must be sorted, you are really just deciding how many of each vowel to use, and the order is determined. The formula C(n + k - 1, k - 1) appears in many counting problems. Once you spot the "distribute identical items into ordered bins" structure, you can skip the DP entirely.

Edge cases

• n = 1: the answer is 5. Each single vowel is trivially sorted. Make sure your DP base case handles this.
• n = 50 (upper constraint): the answer is 316251. Both the O(n) and O(1) solutions handle this instantly, but brute force recursion would time out badly.
• Single vowel available: if you modified the problem to use only 1 vowel, the answer would always be 1 regardless of n. Your DP should degrade gracefully to this case. With 5 vowels, the "u" column already demonstrates this behavior since only one sorted string of any length uses just u.

From understanding to recall

You have seen both the DP and the combinatorics solution, and the connection between them probably makes sense right now. But there is a big gap between following along and producing this from scratch under time pressure. In an interview, nobody tells you "use suffix sums" or "think about stars and bars." You need to see the structure yourself.

Spaced repetition bridges that gap. You revisit this problem at increasing intervals, each time rebuilding the DP table from the recurrence and recognizing the combinatorial structure. After a few reps, the pattern is automatic: "sorted strings from an ordered alphabet" immediately triggers "suffix-sum DP or stars and bars."

This counting-with-constraints pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Climbing Stairs - The simplest DP counting problem, using the same "build from smaller subproblems" idea
• Combination Sum IV - Another counting problem where you sum over all valid choices at each step
• Unique Paths - Grid-based counting that also connects DP to a combinatorics formula