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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Vowel Substrings of a String

Number: 2186

Difficulty: Easy

Paid? No

Companies: Oracle, Snowflake, PayPal, BNY Mellon, Commvault

Problem Description

Given a string, count how many substrings (contiguous sequences of characters) consist entirely of vowels and contain all five vowels at least once.

Key Insights

  • Only vowels ('a', 'e', 'i', 'o', 'u') are allowed in a valid substring.
  • The substring must include every one of the five vowels at least once.
  • As you iterate the string, you can break early from an inner loop when a non-vowel is encountered.
  • Given the constraint (word length up to 100), a nested loop approach is acceptable.

Space and Time Complexity

Time Complexity: O(n^3) in the worst-case scenario (when checking every substring and verifying vowel completeness), but practical performance is better due to early break on non-vowel characters.
Space Complexity: O(1) extra space, aside from input storage.

Solution

We use a brute force approach by iterating through all possible substrings. For each starting index, if the character is a vowel, iterate forward until a non-vowel character is encountered. Maintain a set of vowels seen so far as you extend the substring. When the set contains all five vowels, increment the count.
Key Data Structures:

  • A set to track vowels in the current substring. Algorithm:
  1. Outer loop iterates over possible start indices.
  2. Inner loop generates substrings continuously as long as characters are vowels.
  3. For each valid substring, update the set and check if its size is 5.
  4. If true, increment the answer count.

Code Solutions

# Python solution
def count_vowel_substrings(word: str) -> int:
    vowels = set('aeiou')
    count = 0
    n = len(word)
    # Iterate over each possible starting index
    for i in range(n):
        # Only proceed if the starting character is a vowel
        if word[i] in vowels:
            seen = set()
            # Extend the substring character by character
            for j in range(i, n):
                # Stop if character is not a vowel
                if word[j] not in vowels:
                    break
                # Add the vowel to the set
                seen.add(word[j])
                # If all vowels are present, increment count
                if len(seen) == 5:
                    count += 1
    return count

# Example test
print(count_vowel_substrings("aeiouu"))  # Expected output: 2
← Back to All Questions