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 Vowel Substrings of a String

Difficulty: Easy

Problem Description

Given a string word, return the number of vowel substrings in word. A vowel substring is a substring that only consists of vowels ('a', 'e', 'i', 'o', 'u') and has all five vowels present.

Key Insights

  • A substring is defined as a contiguous sequence of characters within a string.
  • A vowel substring must consist solely of the characters 'a', 'e', 'i', 'o', and 'u'.
  • All five distinct vowels must be present in the substring to qualify as a vowel substring.
  • The problem can be approached by identifying contiguous segments of vowels and checking for the presence of all five vowels within those segments.

Space and Time Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution

To solve the problem, we can use a sliding window approach to identify contiguous segments of vowels. We will maintain a count of the occurrences of each vowel in the current window. As we expand the window by moving the end pointer, we check if all five vowels are present in the current substring. If they are, we can count all the possible valid substrings that can be formed by varying the start pointer while keeping the end pointer fixed. This requires checking and adjusting the counts of vowels in the window as we move the pointers.

Code Solutions

def count_vowel_substrings(word: str) -> int:
    vowels = set('aeiou')
    n = len(word)
    count = 0
    
    for i in range(n):
        if word[i] in vowels:
            vowel_count = {}
            for j in range(i, n):
                if word[j] in vowels:
                    vowel_count[word[j]] = vowel_count.get(word[j], 0) + 1
                    if len(vowel_count) == 5:  # All five vowels are present
                        count += 1
                else:
                    break  # Non-vowel character, stop the inner loop
    return count
← Back to All Questions