Count Sorted Vowel Strings - Video Solutions

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.