#1641

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Sorted Vowel Strings

Calculate the number of length-n strings with vowels only that are sorted lexicographically using state transitions.

Problem Statement

Given an integer n, determine how many strings of length n can be formed using only vowels 'a', 'e', 'i', 'o', and 'u' such that each string is lexicographically non-decreasing.

A string is considered lexicographically sorted if every character is the same as or comes after the previous character in the alphabet. For example, for n = 2, valid strings include "aa", "ae", "ii", while "ea" is invalid because 'e' comes after 'a'. Return the total number of valid strings.

Examples

Example 1

Input: n = 1

Output: 5

The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

Example 2

Input: n = 2

Output: 15

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

Example details omitted.

Constraints

1 <= n <= 50

Solution Approach

Dynamic Programming State Transition

Define dp[i][j] as the number of valid strings of length i ending with the j-th vowel. Each dp[i][j] is the sum of dp[i-1][k] for all k <= j. This ensures the lexicographical order constraint is maintained.

Iterative Table Filling

Start with dp[1][j] = 1 for each vowel since a single character string is always sorted. Then iteratively fill the table for lengths up to n using the state transition formula. The final answer is the sum of dp[n][j] over all vowels.

Combinatorial Optimization

Recognize that this problem can be mapped to "stars and bars" combinatorics. The total count equals C(n+5-1,5-1)=C(n+4,4), which computes directly using combinatorial formulas without building a DP table.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n k) for DP or O(1) for the combinatorial formula, where k=5 vowels. Space is O(n k) for DP or O(1) using combinatorial calculation. The DP approach explicitly demonstrates the state transition pattern for interviews.

What Interviewers Usually Probe

Asks about handling lexicographic constraints efficiently.
Hints at using DP but expects recognition of combinatorial shortcut.
May probe optimization beyond simple DP table.

Common Pitfalls or Variants

Common pitfalls

Confusing lexicographic order and strictly increasing order, leading to incorrect counts.
Failing to account for all previous vowel choices in DP transitions.
Trying to generate all strings instead of counting, causing timeouts for large n.

Follow-up variants

Count sorted consonant strings of length n with similar DP approach.
Compute number of length-n strings with both vowels and consonants sorted.
Generalize to m distinct characters instead of 5 vowels, maintaining DP state transition.

FAQ

What is the pattern behind Count Sorted Vowel Strings?

It follows a state transition dynamic programming pattern where each position depends on allowed previous vowels.

Can this problem be solved without DP?

Yes, using combinatorics with the stars and bars method, computing C(n+4,4) directly.

Why is 'ea' not counted as a valid string for n=2?

Because 'e' comes after 'a', violating the lexicographically sorted constraint.

What is the time complexity of the DP approach?

O(n*5) since each of the n positions sums over 5 vowels.

Can the DP table be reduced in space?

Yes, by using a single array of size 5 and updating in place since only the previous row is needed.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

class Solution:
    def countVowelStrings(self, n: int) -> int:
        @cache
        def dfs(i, j):
            return 1 if i >= n else sum(dfs(i + 1, k) for k in range(j, 5))

        return dfs(0, 0)

Solution 2

#### Python3

1

2

3

4

5

6

7

class Solution:
    def countVowelStrings(self, n: int) -> int:
        @cache
        def dfs(i, j):
            return 1 if i >= n else sum(dfs(i + 1, k) for k in range(j, 5))

        return dfs(0, 0)

Continue Practicing

#1643 kth smallest instructions #1621 number of sets of k non overlapping line segments #1569 number of ways to reorder array to get same bst