LeetCode 1641 - Count Sorted Vowel Strings

LeetCode Problem 1641

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Combinatorics

Solution

Problem Understanding

The problem asks us to count the number of strings of length n composed only of vowels a, e, i, o, u such that each string is lexicographically sorted. Lexicographically sorted means that the characters in the string do not decrease as you move from left to right. For example, ae is valid because a comes before e, but ea is invalid because e comes after a.

The input is a single integer n, representing the length of the string. The output is a single integer representing the total number of valid strings of that length.

The constraints, 1 <= n <= 50, tell us that n is small enough to use combinatorial or dynamic programming approaches but too large to generate all strings naively.

Important edge cases include n = 1, which is trivial because each vowel forms a valid string, and large n values like n = 50, which require a solution that avoids exponential enumeration.

Approaches

Brute Force

A brute-force approach would be to generate all possible strings of length n using the 5 vowels and then filter out those that are not lexicographically sorted. This would involve 5^n possibilities, which becomes infeasible for n as small as 15 or 20. While correct, it is extremely inefficient.

Optimal

The key insight is that for lexicographically sorted strings, the order of vowels does not decrease. This allows us to treat the problem as a combinatorial problem, where we count combinations of vowels with repetition allowed.

Mathematically, the number of such strings of length n using 5 vowels is equivalent to the combination formula:

$$C(n + k - 1, k - 1)$$

where k = 5 is the number of vowels. This formula comes from the combinatorial "stars and bars" theorem, counting the number of ways to distribute n identical items (positions in the string) among 5 distinct categories (vowels) while preserving order.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(5^n)	O(5^n)	Generate all strings and filter
Optimal	O(1)	O(1)	Use combinatorial formula C(n+4,4)

Algorithm Walkthrough

1. Identify that the problem reduces to choosing n items with repetition allowed from 5 vowels while keeping order.
2. Recognize that this is equivalent to the combinatorial problem of choosing 4 dividers among n + 4 positions.
3. Compute the binomial coefficient C(n + 4, 4) using the formula:

$$C(n+4, 4) = \frac{(n+4)(n+3)(n+2)(n+1)}{24}$$

1. Return this value as the result.

Why it works: Every valid string can be represented uniquely by the number of times each vowel appears, and the order of vowels is inherently maintained by counting combinations. This ensures we count all strings exactly once.

Python Solution

class Solution:
    def countVowelStrings(self, n: int) -> int:
        # Using combinatorial formula C(n+4, 4)
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) // 24

This implementation computes the product of four consecutive integers starting from n+1 and divides by 24 (which is 4 factorial) to obtain the binomial coefficient C(n+4,4). It directly follows from the combinatorial reasoning above.

Go Solution

func countVowelStrings(n int) int {
    return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24
}

In Go, integer division is safe here because all intermediate products are divisible by 24, and the result fits within an int for the given constraints. No additional libraries are needed.

Worked Examples

Example 1: n = 1

C(1+4,4) = C(5,4) = 5

Example 2: n = 2

C(2+4,4) = C(6,4) = 15

Example 3: n = 33

C(33+4,4) = C(37,4) = 66045

n	Calculation	Result
1	(5_4_3*2)/24	5
2	(6_5_4*3)/24	15
33	(37_36_35*34)/24	66045

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Formula computation is constant time
Space	O(1)	No extra data structures used

The formula-based approach avoids loops and recursion entirely, ensuring the fastest possible computation for all valid n.

Test Cases

# Provided examples
assert Solution().countVowelStrings(1) == 5  # single vowel strings
assert Solution().countVowelStrings(2) == 15  # length 2 sorted vowel strings
assert Solution().countVowelStrings(33) == 66045  # larger n

# Edge cases
assert Solution().countVowelStrings(50) == 316251  # maximum constraint
assert Solution().countVowelStrings(5) == 126  # moderate size

# Minimal edge case
assert Solution().countVowelStrings(1) == 5  # repeated to validate minimal input

Test	Why
n=1	Minimal input, simplest case
n=2	Small n to verify correctness
n=33	Large n to test calculation
n=50	Maximum n to test upper bound
n=5	Typical case for general validation

Edge Cases

Single-length strings: When n=1, the answer is simply the number of vowels, which is 5. This is handled correctly by the formula.

Maximum-length strings: When n=50, the combinatorial number is large but fits in a standard integer in Python and Go. Using integer division ensures no rounding errors occur.

Repeated characters: Strings like aaaa or eeeee are valid, and the combinatorial approach automatically counts them since it allows repeated selection of the same vowel. This avoids any need for special handling in code.