2062. Count Vowel Substrings of a String - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given a string word. A vowel substring is defined as a contiguous substring of word that:

Consists only of vowels (i.e. the letters 'a', 'e', 'i', 'o', 'u'), and
Contains every one of these vowels at least once.

Return the number of vowel substrings in word.

Example 1:

Input:
word = "aeiouu"
Output: 2
Explanation:
The valid vowel substrings are "aeiou" and "aeiouu".

Example 2:

Input:
word = "unicornarihan"
Output: 0
Explanation:
Although there are vowels in the string, no contiguous substring consisting solely of vowels contains all five vowels.

Example 3:

Input:
word = "cuaieuouac"
Output: 7
Explanation:
There are 7 substrings that consist only of vowels and include all five vowels.
(For example, starting from index 1 and extending while all characters are vowels, certain substrings will eventually contain 'a', 'e', 'i', 'o', and 'u'.)

Constraints:

1 ≤ word.length ≤ 100
word consists only of lowercase English letters.

Hints to Approach the Problem

Hint 1:
Since a vowel substring must contain only vowels, when iterating over word, if you encounter a non-vowel, you can immediately break out of the current substring exploration.
Hint 2:
For each possible starting index that is a vowel, try to extend the substring as long as the characters are vowels. Keep track of which vowels you have seen so far.
Hint 3:
When extending a substring, if the set of vowels seen so far reaches all 5 vowels, then every further extension (until a non-vowel is met) is also a valid vowel substring. Count accordingly.

Approaches

Approach 1: Brute Force with Early Termination

Idea:
For every index i in word (if word[i] is a vowel), extend a substring from i until a non-vowel is encountered. While extending, use a set (or similar) to track the vowels seen.
- If at any point the set has size 5 (contains all vowels), then count the current substring as valid.
- Continue extending (since a longer substring may also be valid) until a non-vowel is reached.
Advantages:
Since the maximum length of word is small (≤ 100), even an O(n²) solution is acceptable.
Details:
– For each starting index that is a vowel, iterate with index j from i forward.
– If word[j] is not a vowel, break out of the inner loop.
– Otherwise, add word[j] to a set and if the set size equals 5, increment your count.

Approach 2: Two Pointers / Sliding Window Variation (Advanced)

Idea:
One could first extract segments that contain only vowels and then, within each segment, count the number of substrings that have all vowels using a sliding window technique.
Notes:
This method can be more efficient in scenarios with long segments of vowels, but for this problem (with small input size) the brute force approach with early termination is straightforward and sufficient.

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
In the worst-case scenario, for every index i (up to n), we extend the substring until the end of the string.
- Worst-case complexity: O(n²).
  Given that n ≤ 100, this is acceptable.
Space Complexity:
We use a set to store vowels seen in a substring. The maximum size of the set is 5 (a constant).
- Overall extra space: O(1).

Step-by-Step Walkthrough

Initialization:
- Define a set of vowels: {'a', 'e', 'i', 'o', 'u'}.
- Initialize a counter count to 0.
- Iterate through each index i in the string.
Starting a Substring:
- For each index i, check if word[i] is a vowel. If not, skip to the next index.
- If it is a vowel, initialize an empty set seen.
Expanding the Substring:
- For each index j starting from i:
  - If word[j] is not a vowel, break out of the inner loop.
  - Otherwise, add word[j] to the set seen.
  - Check if the size of seen equals 5 (meaning all vowels have been encountered).
  - If yes, increment the count.
Termination:
- Continue until all possible starting indices are processed.
- Return the final count.

Visual Example

Let’s take word = "cuaieuouac" as an example:

Index 0:
Character 'c' is not a vowel → skip.
Index 1:
Character 'u' is a vowel. Start a new substring:
- Substring starting at index 1: "u" → seen = {u} (not all vowels)
- Extend to index 2: "ua" → seen = {u, a}
- Extend to index 3: "uai" → seen = {u, a, i}
- Extend to index 4: "uaie" → seen = {u, a, i, e}
- Extend to index 5: "uaieu" → seen = {u, a, i, e} (still missing 'o')
- Extend to index 6: "uaieuo" → seen = {u, a, i, e, o} (all vowels present) → count++
- Continue extending while vowels continue; every additional character (until a non-vowel) forms a valid substring.
Subsequent Starting Indices:
The algorithm similarly processes other valid starting indices that are vowels and counts every valid substring.

In total, for this word, the algorithm would count 7 valid vowel substrings.

Common Mistakes

Not Breaking on Non-Vowel:
Forgetting to break out of the inner loop when a non-vowel is encountered can lead to incorrect substrings being considered.
Incorrect Vowel Check:
Ensure that only the characters 'a', 'e', 'i', 'o', and 'u' are treated as vowels.
Overcounting Substrings:
Carefully count each substring only once while extending from a valid starting index.

Edge Cases

No Vowel Substrings:
When word does not contain any substring that is made up entirely of vowels or does not include all five vowels, the answer should be 0.
Single Character Word:
A single vowel character cannot form a valid substring since it doesn’t contain all vowels.
Short Segments of Vowels:
Segments of consecutive vowels that are shorter than 5 characters should not be counted.

Sliding Window Problems:
Counting substrings or subarrays with a certain property using a sliding window.
Substring Counting Problems:
Problems that require counting substrings based on specific criteria (e.g., containing distinct characters).

Longest Substring Without Repeating Characters
Subarray Sum Equals K
Count Number of Nice Subarrays