#2062

Easy

LeetCode Problem Workspace

Count Vowel Substrings of a String

Count the number of vowel substrings that include all five vowels in a string.

Problem Statement

Given a string word, find the number of vowel substrings that include all five vowels ('a', 'e', 'i', 'o', 'u').

A substring is defined as a contiguous non-empty sequence of characters within the string. Vowel substrings are those containing only vowels and must contain all five vowels at least once.

Examples

Example 1

Input: word = "aeiouu"

Output: 2

The vowel substrings of word are as follows (underlined):

"aeiouu"
"aeiouu"

Example 2

Input: word = "unicornarihan"

Output: 0

Not all 5 vowels are present, so there are no vowel substrings.

Example 3

Input: word = "cuaieuouac"

Output: 7

The vowel substrings of word are as follows (underlined):

"cuaieuouac"
"cuaieuouac"
"cuaieuouac"
"cuaieuouac"
"cuaieuouac"
"cuaieuouac"
"cuaieuouac"

Constraints

1 <= word.length <= 100
word consists of lowercase English letters only.

Solution Approach

Sliding Window and Hash Table

Use a sliding window approach combined with a hash table to track the vowels as you iterate through the string. The hash table can store counts of the vowels in the current window. Adjust the window size dynamically as you encounter consonants or reach the required condition of containing all vowels.

Early Termination on Consonants

As you generate substrings starting from each index, skip larger substrings if you encounter a consonant. This reduces unnecessary checks and avoids generating non-vowel substrings.

Efficient Counting of Vowel Substrings

For each valid window containing all five vowels, count all substrings that start within this window. This can be done efficiently by calculating how many substrings start from each valid index within the window.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for substring generation. A sliding window approach can optimize it to O(n), where n is the length of the string. The space complexity depends on the hash table storage, which can be O(1) due to the fixed size of vowel sets.

What Interviewers Usually Probe

Can the candidate optimize the solution to avoid unnecessary checks for consonants?
Does the candidate understand how to efficiently count substrings starting from any index in the window?
Can the candidate effectively manage and update the window boundaries with a hash table?

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle consonants and continuing substring generation unnecessarily.
Failing to properly update the window boundaries when encountering consonants.
Overcomplicating the counting process for substrings when the solution can be simplified using efficient window tracking.

Follow-up variants

Consider variants where the string contains no vowels and test the candidate's ability to handle edge cases.
Test how the candidate handles cases where the string has multiple vowels, but not all five present.
Explore the case where substrings must be of a specific length or meet other constraints.

FAQ

How do I efficiently count vowel substrings in this problem?

Use a sliding window combined with a hash table to track the vowels. As soon as all five vowels are in the window, count all substrings that start within it.

What if my string doesn't contain all five vowels?

In that case, the number of vowel substrings will be zero, as all five vowels are required for the substring to be valid.

What is the time complexity of this problem?

With the sliding window approach and hash table, the time complexity is O(n), where n is the length of the string.

What are common mistakes people make in this problem?

Common mistakes include failing to skip generating substrings with consonants and not efficiently counting substrings from valid windows.

Can I use other data structures for this problem?

While hash tables and sliding windows are optimal for this problem, other methods like brute force are less efficient for larger inputs.

terminal

Solution

Solution 1: Brute Force Enumeration + Hash Table

We can enumerate the left endpoint $i$ of the substring. For the current left endpoint, maintain a hash table to record the vowels that appear in the current substring. Then enumerate the right endpoint $j$. If the character at the current right endpoint is not a vowel, break the loop. Otherwise, add the character at the current right endpoint to the hash table. If the number of elements in the hash table is $5$, it means the current substring is a vowel substring, and increment the result by $1$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def countVowelSubstrings(self, word: str) -> int:
        s = set("aeiou")
        ans, n = 0, len(word)
        for i in range(n):
            t = set()
            for c in word[i:]:
                if c not in s:
                    break
                t.add(c)
                ans += len(t) == 5
        return ans

Continue Practicing

#2068 check whether two strings are almost equivalent #2053 kth distinct string in an array #2085 count common words with one occurrence