Count Vowel Substrings

Enumerate vowel-only slices

Try every starting position. Extend right until a consonant blocks the slice, recording the vowel types you meet. Once all five types have appeared, this endpoint and every later endpoint before the next consonant can contribute an answer.

def count_vowel_substrings(word: str) -> int:
    vowels = set("aeiou")
    total = 0
 
    for start in range(len(word)):
        seen: set[str] = set()
        for end in range(start, len(word)):
            char = word[end]
            if char not in vowels:
                break
            seen.add(char)
            if len(seen) == 5:
                total += 1
 
    return total

Time O(n²) in a long vowel-only string. Space O(1) because seen holds at most five characters.

Vowel-run sliding window

A maximal vowel run is an uninterrupted block of vowels bordered by consonants or the ends of the string. Process each run with one window.

Keep a count for each vowel, plus distinct, the number of vowel types currently in the window. When all five are present, move left past duplicate copies while preserving at least one of every type. The window is now tight: moving left again would lose a required vowel.

For the current right, every start from run_start through left is valid. There are left - run_start + 1 such starts. A consonant clears the five counters and starts a new run.

def count_vowel_substrings(word: str) -> int:
    vowel_index = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
    counts = [0] * 5
    distinct = 0
    left = 0
    run_start = 0
    total = 0
 
    for right, char in enumerate(word):
        index = vowel_index.get(char)
        if index is None:
            counts = [0] * 5
            distinct = 0
            left = right + 1
            run_start = right + 1
            continue
 
        if counts[index] == 0:
            distinct += 1
        counts[index] += 1
 
        if distinct == 5:
            left_index = vowel_index[word[left]]
            while counts[left_index] > 1:
                counts[left_index] -= 1
                left += 1
                left_index = vowel_index[word[left]]
            total += left - run_start + 1
 
    return total

Why count all starts through left? The tight window proves the slice beginning at left has all five vowels. Starting earlier stays inside the same vowel run and only adds vowels, so those starts work too. Starting later drops the leftmost required vowel.

Time O(n) — right and left each move forward only. Space O(1) for five fixed counters and the vowel lookup.