# LeetCode 1641. Count Sorted Vowel Strings

## Description

https://leetcode.com/problems/count-sorted-vowel-strings/

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`

## Explanation

We can use an approach similar to what we use for Combination Sum to solve this problem. Use backtracking approach to find all vowels combinations with length at n.

## Python Solution

``````class Solution:
def countVowelStrings(self, n: int) -> int:

vowels = ['a', 'e', 'i', 'o', 'u']

results = []

self.helper(vowels, n, results, "", 0)

return len(results)

def helper(self, vowels, n, results, combination, start):
if len(combination) == n:
results.append(combination)
return

for i in range(start, len(vowels)):
c = vowels[i]

combination += c

self.helper(vowels, n, results, combination, i)

combination = combination[:-1]
``````
• Time Complexity: O(N).
• Space Complexity: O(N).