# Count Sorted Vowel Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-sorted-vowel-strings)
Canonical: https://scaleengineer.com/dsa/problems/count-sorted-vowel-strings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
---
## Problem
Given an integer `n`, return _the number of strings of length_ `n` _that consist only of vowels (_`a`_,_ `e`_,_ `i`_,_ `o`_,_ `u`_) and are **lexicographically sorted**._

A string `s` is **lexicographically sorted** if for all valid `i`, `s[i]` is the same as or comes before `s[i+1]` in the alphabet.

**Example 1:**

**Input:** n = 1
**Output:** 5
**Explanation:** The 5 sorted strings that consist of vowels only are `["a","e","i","o","u"].`

**Example 2:**

**Input:** n = 2
**Output:** 15
**Explanation:** 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

**Constraints:**

* `1 <= n <= 50`

# Approaches
## Brute-force Backtracking
A straightforward approach is to use backtracking to generate all possible sorted vowel strings of length `n` and count them. We can build the strings character by character, ensuring that each new character is greater than or equal to the previous one. This naturally leads to a recursive solution.
**Time:** Exponential - The time complexity is roughly O(k^n) where k is the number of vowels (5). The function branches for each position in the string, leading to an exponential number of calls. This is too slow for the given constraints. · **Space:** O(n) - The space complexity is determined by the maximum depth of the recursion stack, which is proportional to `n`.
**Pros:** Simple to conceptualize and implement.; It's a direct translation of the problem's constraints into code.
**Cons:** Extremely inefficient due to a large number of redundant calculations.; Will result in a 'Time Limit Exceeded' (TLE) error for larger values of `n` (like n > 15).
### Explanation
We can define a recursive function that builds the string. The state of our recursion can be defined by `(current_length, last_vowel_index)`. The `current_length` tracks the length of the string built so far, and `last_vowel_index` tracks the last vowel added to maintain the sorted order. The function would explore adding all valid subsequent vowels. When the `current_length` reaches `n`, we've successfully constructed one valid string and increment our total count.

```java
class Solution {
    public int countVowelStrings(int n) {
        return count(n, 0);
    }

    private int count(int length, int lastVowelIndex) {
        // Base case: if a string of the desired length is formed, we found one valid string.
        if (length == 0) {
            return 1;
        }

        int total = 0;
        // Iterate through the vowels that can be placed at the current position.
        // To maintain lexicographical order, the next vowel must be the same as or come after the last one.
        for (int i = lastVowelIndex; i < 5; i++) {
            total += count(length - 1, i);
        }
        return total;
    }
}
```
### Algorithm
1. Define a recursive function, let's call it `generateAndCount`, that takes the current string length `n` and the index of the last vowel used `lastVowelIndex`.
2. The `lastVowelIndex` helps ensure the lexicographical order. For the next character, we can only pick vowels from `lastVowelIndex` onwards.
3. The base case for the recursion is when the desired length `n` is reached. In this case, we have found one valid string, so we return 1.
4. In the recursive step, we iterate through the vowels starting from `lastVowelIndex`. For each vowel, we make a recursive call for a string of length `n-1`, passing the current vowel's index.
5. The total count is the sum of the results from all these recursive calls.
6. The initial call would be to a helper function that starts the process for length `n` and allows any vowel to be the first character.

## Dynamic Programming
The backtracking approach involves many overlapping subproblems. For instance, `count(k, vowel_index)` is calculated multiple times. We can optimize this using dynamic programming. We can use a 2D array, say `dp[i][j]`, to store the number of sorted strings of length `i` that can be formed using a specific set of `j` vowels. This avoids re-computation and significantly improves performance.
**Time:** O(n*k) where k=5. We iterate through the DP table of size `n x 5`. Since `k` is constant, this is O(n). · **Space:** O(n*k) where k=5. We use a 2D DP table of size `(n+1) x 6`. Since `k` is constant, this is O(n).
**Pros:** Efficient with a polynomial time complexity.; Guaranteed to pass within the time limits.; Systematic and easy to debug.
**Cons:** Uses more space than necessary.
### Explanation
Let's define `dp[i][j]` as the number of sorted strings of length `i` that are formed using the first `j` vowels from the set {'a', 'e', 'i', 'o', 'u'}. For example, `dp[i][1]` would be strings made only of 'a', `dp[i][2]` would be strings made of 'a' and 'e'.

The recurrence relation can be established as follows: A sorted string of length `i` using the first `j` vowels can either:
1. Not contain the `j`-th vowel. In this case, it's a sorted string of length `i` using the first `j-1` vowels. The count is `dp[i][j-1]`.
2. Contain the `j`-th vowel. Since the string is sorted, if it contains the `j`-th vowel, we can think of it as taking a sorted string of length `i-1` (using the first `j` vowels) and appending the `j`-th vowel. This is not quite right. A better way to think about it is `dp[i][j] = dp[i-1][j] + dp[i][j-1]`, which is a common DP pattern for this type of problem.

We can implement this using a bottom-up approach with a 2D table.

```java
class Solution {
    public int countVowelStrings(int n) {
        // dp[i][j]: number of strings of length i using first j vowels
        int[][] dp = new int[n + 1][6];

        // Base cases
        for (int j = 1; j <= 5; j++) {
            dp[1][j] = j;
        }
        for (int i = 1; i <= n; i++) {
            dp[i][1] = 1;
        }

        // Fill DP table
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= 5; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[n][5];
    }
}
```
Alternatively, a top-down approach with memoization can be used to optimize the recursive solution, achieving the same time and space complexity.
### Algorithm
1. Let `dp[i][j]` be the number of sorted vowel strings of length `i` using the first `j` vowels (e.g., `j=1` for {'a'}, `j=2` for {'a', 'e'}, etc.).
2. The recurrence relation is `dp[i][j] = dp[i-1][j] + dp[i][j-1]`.
   - `dp[i-1][j]`: Count of strings of length `i-1` using the first `j` vowels. We can append the `j`-th vowel to each of these to form valid strings of length `i`.
   - `dp[i][j-1]`: Count of strings of length `i` that only use the first `j-1` vowels.
3. Base Cases:
   - `dp[i][1] = 1` for all `i > 0` (only one string is possible with just 'a': "aaa...").
   - `dp[1][j] = j` for all `j > 0` (strings of length 1: 'a', 'e', ..., `j`-th vowel).
4. We can build a 2D DP table of size `(n+1) x 6` and fill it iteratively.
5. The final answer is `dp[n][5]`.

## Space-Optimized Dynamic Programming
Looking at the DP recurrence `dp[i][j] = dp[i-1][j] + dp[i][j-1]`, we can see that the calculation for the current row `i` only depends on values from the previous row `i-1` and the current row `i`. This allows for a space optimization. Instead of storing the entire 2D table, we only need to keep track of the previous row's results to compute the current row, reducing the space complexity significantly.
**Time:** O(n*k) where k=5. Since `k` is a constant, the time complexity is O(n). · **Space:** O(k) where k=5. Since `k` is a constant, the space complexity is O(1).
**Pros:** Highly efficient in both time and space.; Optimal among iterative solutions.
**Cons:** The logic can be slightly less intuitive than the 2D DP approach.
### Explanation
We can use a single 1D array `dp` of size `k` (where `k=5` is the number of vowels) to store the counts for the current string length. Let's refine the DP state slightly: `dp[j]` will be the number of sorted strings of length `i` ending with the `j`-th vowel.

For `n=1`, the counts are `[1, 1, 1, 1, 1]` (for strings "a", "e", "i", "o", "u").
For `n=2`, a string ending in 'a' must be "aa". A string ending in 'e' can be "ae" or "ee". A string ending in 'i' can be "ai", "ei", "ii".
We can see a pattern: `dp[j]` for the current length is the sum of `dp[k]` from the previous length, where `k <= j`.
This is equivalent to a prefix sum. `dp[j] = dp[j] + dp[j-1]` in a loop.

```java
class Solution {
    public int countVowelStrings(int n) {
        // dp[j] will store the number of sorted strings of length i ending with vowel j
        int[] dp = new int[5];
        // Initialize for n=1
        for (int j = 0; j < 5; j++) {
            dp[j] = 1;
        }

        // Iterate for lengths from 2 to n
        for (int i = 2; i <= n; i++) {
            // Update counts based on previous length's counts
            // This is a running prefix sum
            for (int j = 1; j < 5; j++) {
                dp[j] = dp[j] + dp[j-1];
            }
        }

        // The total is the sum of all counts for length n
        int total = 0;
        for (int count : dp) {
            total += count;
        }
        return total;
    }
}
```
### Algorithm
1. Notice that to compute the `i`-th row of our DP table, we only need the `(i-1)`-th row.
2. We can reduce the space from a 2D array to a 1D array, say `dp` of size 6.
3. Initialize `dp` with all 1s. This represents the base case for strings of length 0 (there's one empty string for any vowel set).
4. Iterate from `i = 1` to `n` (representing the string length).
5. In an inner loop, iterate from `j = 1` to `5` (representing the number of vowels used).
6. Apply the optimized recurrence: `dp[j] = dp[j] + dp[j-1]`. Here, the old `dp[j]` represents `dp[i-1][j]` and the new `dp[j-1]` represents `dp[i][j-1]`.
7. After the loops, `dp[5]` will hold the final answer.

## Combinatorics (Stars and Bars)
The most efficient solution comes from a mathematical or combinatorial perspective. The problem asks for the number of lexicographically sorted strings. This means that for any multiset of `n` vowels, there is exactly one way to arrange them to form a valid string. For example, if we choose the vowels {'e', 'a', 'u'} for `n=3`, the only sorted string is "aeu".

Therefore, the problem is equivalent to asking: "How many ways can we choose `n` vowels from the set {'a', 'e', 'i', 'o', 'u'} with replacement?"
**Time:** O(1) - The result is computed using a fixed number of arithmetic operations, regardless of the value of `n`. · **Space:** O(1) - No extra space is used that depends on the input `n`.
**Pros:** The most efficient solution with constant time and space complexity.; Provides a direct formula for the answer.
**Cons:** Requires mathematical insight that might not be immediately obvious.; The intermediate product `(n+4)*(n+3)*(n+2)*(n+1)` could overflow standard integer types for very large `n`, though it's fine for the given constraints (`n <= 50`).
### Explanation
This is a classic "Stars and Bars" problem in combinatorics. Imagine we have `n` stars (`*`), each representing a position in the string. We want to assign a vowel to each star. We can use `k-1` bars (`|`) to partition the stars into `k` groups, where `k=5` is the number of vowels. Each group represents the count of a specific vowel.

For example, with `n=3` and `k=5`, the arrangement `* | * | * | |` corresponds to one 'a', one 'e', one 'i', zero 'o's, and zero 'u's, which forms the string "aei". The arrangement `*** | | | |` corresponds to three 'a's, forming "aaa".

We have a total of `n` stars and `k-1 = 4` bars. The total number of items to arrange is `n + 4`. The problem reduces to choosing `4` positions for the bars out of `n + 4` available positions. The formula for combinations is `C(m, r) = m! / (r! * (m-r)!)`.

Here, `m = n + 4` and `r = 4`. So the count is `C(n + 4, 4)`.

`C(n + 4, 4) = (n + 4)! / (4! * (n + 4 - 4)!) = (n + 4)! / (4! * n!) = ((n + 4) * (n + 3) * (n + 2) * (n + 1)) / (4 * 3 * 2 * 1)`

```java
class Solution {
    public int countVowelStrings(int n) {
        // This is a combination with repetition problem.
        // The formula is C(n + k - 1, k - 1), where n is the length of the string
        // and k is the number of vowels (5).
        // So, C(n + 5 - 1, 5 - 1) = C(n + 4, 4).
        // C(n + 4, 4) = (n + 4) * (n + 3) * (n + 2) * (n + 1) / (4 * 3 * 2 * 1)
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
    }
}
```
### Algorithm
1. Reframe the problem: We need to choose `n` characters from the 5 vowels, with replacement, and the order of selection doesn't matter because there's only one way to sort them.
2. This is a classic combinatorial problem known as "combinations with repetition".
3. The problem is equivalent to finding the number of ways to put `n` identical items (stars) into `k` distinct bins (vowels). Here `n` is the string length and `k=5`.
4. The formula for this is `C(n + k - 1, k - 1)` or `C(n + k - 1, n)`.
5. Substitute `k=5`: `C(n + 5 - 1, 5 - 1) = C(n + 4, 4)`.
6. Calculate the result: `(n + 4) * (n + 3) * (n + 2) * (n + 1) / (4 * 3 * 2 * 1)`.

# Solutions
### Java

```java
class Solution { private Integer [][] f ; private int n ; public int countVowelStrings ( int n ) { this . n = n ; f = new Integer [ n ][ 5 ]; return dfs ( 0 , 0 ); } private int dfs ( int i , int j ) { if ( i >= n ) { return 1 ; } if ( f [ i ][ j ] != null ) { return f [ i ][ j ]; } int ans = 0 ; for ( int k = j ; k < 5 ; ++ k ) { ans += dfs ( i + 1 , k ); } return f [ i ][ j ] = ans ; } }
```

### CPP

```cpp
class Solution { public: int countVowelStrings ( int n ) { int f [ n ][ 5 ]; memset ( f , 0 , sizeof f ); function < int ( int , int ) > dfs = [ & ]( int i , int j ) { if ( i >= n ) { return 1 ; } if ( f [ i ][ j ]) { return f [ i ][ j ]; } int ans = 0 ; for ( int k = j ; k < 5 ; ++ k ) { ans += dfs ( i + 1 , k ); } return f [ i ][ j ] = ans ; }; return dfs ( 0 , 0 ); } };
```

### Python

```python
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 )
```