We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Sorted Vowel Strings

Difficulty: Medium

Problem Description

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.

Key Insights

  • The strings can only consist of the vowels: a, e, i, o, u.
  • A lexicographically sorted string means that the character at position i must be less than or equal to the character at position i+1.
  • The problem can be approached using combinatorial mathematics, specifically by using combinatorics to find the number of ways to choose positions for vowels while maintaining their order.

Space and Time Complexity

Time Complexity: O(1) - The solution can be computed in constant time using combinatorial formulas. Space Complexity: O(1) - No extra space is used that grows with input size.

Solution

To solve the problem, we can use the combinatorial approach where the number of sorted vowel strings of length n can be represented as the number of ways to distribute n identical items (vowels) into 5 distinct bins (the vowels a, e, i, o, u). This can be calculated using the formula for combinations: C(n + k - 1, k - 1), where n is the length of the strings and k is the number of types of vowels (which is 5).

Using this formula, we can compute the answer directly.

Code Solutions

def countVowelStrings(n: int) -> int:
    # The number of vowels
    vowels = 5
    # Using the combinatorial formula C(n + k - 1, k - 1)
    # where k is the number of vowels (5)
    return (n + vowels - 1) * (n + vowels - 2) // 2

# Example usage
print(countVowelStrings(1))  # Output: 5
print(countVowelStrings(2))  # Output: 15
print(countVowelStrings(33)) # Output: 66045
← Back to All Questions