LeetCode 1641. Count Sorted Vowel Strings



Given an integer n, return the number of strings of length n that consist only of vowels (aeiou) and are lexicographically sorted.

A string s is lexicographically sorted if for all valid is[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
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

Example 3:

Input: n = 33
Output: 66045


  • 1 <= n <= 50 


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:
        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).

Leave a Reply

Your email address will not be published. Required fields are marked *