Count Sorted Vowel Strings
Problem
Return the number of strings of length n consisting only of vowels (a, e, i, o, u) that are sorted in lexicographic order.
n = 215def count_vowel_strings(n):
# dp[v] = number of sorted strings ending with vowel v (a=0..u=4)
dp = [1] * 5
for _ in range(n - 1):
for v in range(3, -1, -1):
dp[v] += dp[v + 1]
return sum(dp)function countVowelStrings(n) {
const dp = [1, 1, 1, 1, 1];
for (let k = 1; k < n; k++)
for (let v = 3; v >= 0; v--)
dp[v] += dp[v + 1];
return dp.reduce((a, b) => a + b, 0);
}class Solution {
public int countVowelStrings(int n) {
int[] dp = {1, 1, 1, 1, 1};
for (int k = 1; k < n; k++)
for (int v = 3; v >= 0; v--)
dp[v] += dp[v + 1];
int s = 0;
for (int x : dp) s += x;
return s;
}
}int countVowelStrings(int n) {
int dp[5] = {1, 1, 1, 1, 1};
for (int k = 1; k < n; k++)
for (int v = 3; v >= 0; v--)
dp[v] += dp[v + 1];
int s = 0;
for (int x : dp) s += x;
return s;
}Explanation
A "sorted" vowel string just means the letters never go backwards (like aae or iou). The neat idea is to track, for each ending vowel, how many sorted strings of the current length finish with that vowel — then grow the length one step at a time.
We start with dp = [1, 1, 1, 1, 1] for the five vowels a, e, i, o, u: there is exactly one length-1 string ending in each.
To extend by one character, a string ending in vowel v can be followed by v itself or any later vowel. Sweeping from right to left, dp[v] += dp[v + 1] turns each entry into a running suffix sum, so dp[v] becomes the count of strings whose next allowed letter is v or beyond.
We repeat this n - 1 times, then add up all five entries to get the total number of sorted strings of length n.
Example: n = 2. After one update the array becomes [5, 4, 3, 2, 1], which sums to 15 — the 15 sorted two-letter vowel strings.