Problem Description

You need to find and count all special substrings in a given string that meet two specific criteria:

1. The substring must contain only vowels ('a', 'e', 'i', 'o', 'u')
2. The substring must contain all five vowels at least once

A substring is a continuous sequence of characters from the original string. For example, in the string "hello", some substrings are "h", "he", "ell", "llo", etc.

The task is to count how many such "vowel substrings" exist in the input string word.

For example:

• If word = "aeiouu", there are 2 valid vowel substrings: "aeiou" and "aeiouu" (both contain all 5 vowels and only vowels)
• If word = "unicornarihan", there are 0 valid vowel substrings (no substring contains all 5 vowels using only vowel characters)

The solution works by:

1. Checking every possible starting position i in the string
2. For each starting position, extending rightward character by character
3. Tracking which vowels have been seen using a set t
4. If a non-vowel is encountered, stopping the current extension
5. When all 5 vowels are present (checked by len(t) == 5), counting it as a valid vowel substring
6. Continuing to extend rightward to find more valid substrings from the same starting position

The time complexity is O(n²) where n is the length of the string, since we examine all possible substrings that contain only vowels.

Intuition

The key insight is that we need to find substrings that satisfy two constraints simultaneously: containing only vowels AND containing all five vowels. This suggests we need to track two things as we explore substrings: whether each character is a vowel, and which vowels we've seen so far.

Since we need contiguous substrings, a natural approach is to consider all possible starting positions and extend from each one. For any starting position i, we can try to extend the substring by adding characters one by one to the right.

Why does this make sense? Because:

1. If we hit a consonant at any point, we know that no substring starting at i and extending beyond that consonant can be valid (it would contain a non-vowel)
2. We need to keep track of which vowels we've collected so far - a set is perfect for this since it automatically handles duplicates
3. Once we have all 5 vowels in our set, every extension that still contains only vowels gives us another valid substring

The beauty of this approach is its simplicity - we don't need complex data structures or algorithms. We just systematically check every possible vowel-only substring and count those that contain all five vowels.

The condition len(t) == 5 is elegant because it automatically tells us when we've seen all five distinct vowels (since the set only stores unique elements). Every time this condition becomes true as we extend our substring, we've found another valid vowel substring to count.

This brute force approach works well here because the constraint (containing only vowels) naturally limits how far we need to search from each starting position - we stop as soon as we hit a consonant.

Solution Approach

The solution uses a brute force enumeration approach combined with a hash table (set) to track vowels.

Step-by-step implementation:

1. Initialize the vowel set: Create a set s containing all five vowels "aeiou" for quick vowel checking using O(1) lookup time.

2. Set up variables: Initialize ans = 0 to count valid substrings and get the string length n.

3. Enumerate left endpoints: Use the outer loop with index i from 0 to n-1 to represent each possible starting position of a substring.

4. Track vowels for current substring: For each starting position i, create an empty set t to track which distinct vowels appear in the current substring being built.

5. Extend the substring rightward: The inner loop iterates through characters starting from position i using slice notation word[i:]. For each character c:

   • Check if it's a vowel: If c not in s, the character is a consonant, so we break immediately since no valid substring can extend beyond this point
   • Add vowel to tracking set: If it's a vowel, add it to set t using t.add(c)
   • Check for valid substring: After adding the vowel, check if len(t) == 5. If true, we have all five vowels, making this a valid vowel substring, so increment ans += 1

6. Return the count: After examining all possible substrings, return ans.

Why this works:

• The nested loop structure ensures we check every possible substring that starts with a vowel
• The set t automatically handles duplicate vowels - we only care about having each vowel type at least once
• Breaking on consonants optimizes the search by avoiding unnecessary iterations
• The condition ans += len(t) == 5 is a concise way to increment the counter (adds 1 when true, 0 when false)

Time Complexity: O(n²) where n is the length of the string, as we potentially examine all substrings. Space Complexity: O(1) since the sets can contain at most 5 elements.

Example Walkthrough

Let's trace through the algorithm with word = "aeioubbb".

Initial Setup:

• s = {'a', 'e', 'i', 'o', 'u'} (vowel set for checking)
• ans = 0 (counter for valid substrings)
• n = 8 (length of "aeioubbb")

Iteration with i = 0 (starting at 'a'):

• Initialize t = {} (empty set to track vowels)
• Examine substring starting from index 0:
  • Character 'a': Is vowel ✓, add to t → t = {'a'}, len(t) = 1 ≠ 5
  • Character 'e': Is vowel ✓, add to t → t = {'a', 'e'}, len(t) = 2 ≠ 5
  • Character 'i': Is vowel ✓, add to t → t = {'a', 'e', 'i'}, len(t) = 3 ≠ 5
  • Character 'o': Is vowel ✓, add to t → t = {'a', 'e', 'i', 'o'}, len(t) = 4 ≠ 5
  • Character 'u': Is vowel ✓, add to t → t = {'a', 'e', 'i', 'o', 'u'}, len(t) = 5 ✓, ans = 1 (found "aeiou")
  • Character 'b': Not a vowel ✗, break inner loop

Iteration with i = 1 (starting at 'e'):

• Initialize t = {}
• Examine substring starting from index 1:
  • Character 'e': Is vowel ✓, add to t → t = {'e'}, len(t) = 1 ≠ 5
  • Character 'i': Is vowel ✓, add to t → t = {'e', 'i'}, len(t) = 2 ≠ 5
  • Character 'o': Is vowel ✓, add to t → t = {'e', 'i', 'o'}, len(t) = 3 ≠ 5
  • Character 'u': Is vowel ✓, add to t → t = {'e', 'i', 'o', 'u'}, len(t) = 4 ≠ 5
  • Character 'b': Not a vowel ✗, break inner loop

Iterations i = 2, 3, 4: Similar pattern - each builds a set of vowels but never reaches all 5 before hitting 'b'

Iterations i = 5, 6, 7 (starting at 'b'):

• First character 'b' is not a vowel, immediately break inner loop

Final Result: ans = 1

The algorithm found exactly one valid vowel substring: "aeiou" (from indices 0-4).

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the string word. This is because we have two nested loops: the outer loop iterates through each starting position i from 0 to n-1, and for each starting position, the inner loop iterates through the substring starting at position i to potentially the end of the string. In the worst case, for each of the n starting positions, we examine up to n characters, resulting in O(n * n) = O(n^2) operations.

The space complexity is O(C), where C is the size of the character set. In this problem, we use two sets: s which stores the 5 vowels ("aeiou"), and t which accumulates the vowels found in the current substring. Since both sets can contain at most 5 distinct vowel characters, the space complexity is O(5) = O(1), which can be generalized as O(C) where C = 5 represents the number of distinct vowels.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Substring Counting

The Problem: A common mistake is thinking that once we find all 5 vowels from a starting position, we should stop checking and move to the next starting position. This would miss valid substrings that extend beyond the first occurrence of all 5 vowels.

Incorrect Approach:

for start_index in range(word_length):
    found_vowels = set()
    for char in word[start_index:]:
        if char not in vowels:
            break
        found_vowels.add(char)
        if len(found_vowels) == 5:
            count += 1
            break  # WRONG: Breaking here misses longer valid substrings

Why it's wrong: Consider the string "aeiouu". From position 0:

• "aeiou" is valid (count = 1)
• "aeiouu" is also valid (count = 2)

Breaking after finding the first valid substring would miss "aeiouu".

Correct Solution: Continue extending the substring even after finding all 5 vowels, as shown in the original code. Each extension that still contains all 5 vowels is a distinct valid substring.

Pitfall 2: Using Index-Based Inner Loop Incorrectly

The Problem: Using indices for both loops but forgetting to adjust the inner loop's range can lead to incorrect results or inefficiency.

Incorrect Approach:

for i in range(word_length):
    found_vowels = set()
    for j in range(word_length):  # WRONG: Should start from i
        if word[j] not in vowels:
            break
        found_vowels.add(word[j])
        if len(found_vowels) == 5:
            count += 1

Why it's wrong: This examines the same prefix repeatedly instead of different substrings starting at position i.

Correct Solution: Either use range(i, word_length) for the inner loop or use slice notation word[i:] as in the original solution:

for i in range(word_length):
    found_vowels = set()
    for j in range(i, word_length):  # Correct: Start from i
        if word[j] not in vowels:
            break
        found_vowels.add(word[j])
        if len(found_vowels) == 5:
            count += 1

Pitfall 3: Resetting the Vowel Tracker Incorrectly

The Problem: Forgetting to reset the vowel tracking set for each new starting position, or resetting it at the wrong time.

Incorrect Approach:

found_vowels = set()  # WRONG: Declared outside the outer loop
for start_index in range(word_length):
    for char in word[start_index:]:
        if char not in vowels:
            found_vowels = set()  # WRONG: Reset only on consonant
            break
        found_vowels.add(char)
        if len(found_vowels) == 5:
            count += 1

Why it's wrong: The set should be fresh for each new starting position, not carried over from previous iterations or reset only when hitting a consonant.

Correct Solution: Initialize found_vowels = set() inside the outer loop but before the inner loop, ensuring each starting position gets a clean slate for tracking vowels.