Count Vowel Substrings of a String — Medium Problem & Solution

A vowel substring is a contiguous substring made up only of vowels (a, e, i, o, u) that contains all five of them at least once.

Difficulty: Medium
Topics: Strings, Hash Table, Sliding Window
Asked at: Amazon, Google, Cognizant
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A vowel substring is a contiguous substring made up only of vowels (a, e, i, o, u) that contains all five of them at least once.

Return the number of vowel substrings of word.

Example 1

Input: word = "aeiouu"
Output: 2
Explanation: `aeiou` and `aeiouu`.

Example 2

Input: word = "codekairo"
Output: 0
Explanation: Consonants break every run, so no all-vowel substring exists.

Example 3

Input: word = "cuaieuouac"
Output: 7

Constraints

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

How to solve Count Vowel Substrings of a String

For each start index, extend a window right while the characters remain vowels, tracking how many distinct vowels have been seen. Every extension after the fifth distinct vowel arrives is another valid substring.

Approach

For each i, reset a set of seen vowels.
Extend j from i; break out on a consonant.
Count the substring whenever the set holds all five vowels.

Why it works

Breaking on a consonant is what keeps this near-linear in practice — the inner loop never crosses one, so the total work is the sum of the squares of the vowel-run lengths, not n². The sliding-window version tracks the smallest window covering all five and adds its left-extension count, which is O(n) but far harder to get exactly right.

Complexity

Time — O(n²) in the worst case, and much less when consonants are common
Space — O(1) — at most five distinct vowels

Pitfalls

The substring must contain no consonants, not merely start and end with vowels.
All five vowels are required — four is not enough.
Longer substrings that still qualify each count separately.

Reference solution

Python

def countVowelSubstrings(word: str) -> int:
    vowels = set("aeiou")
    count = 0
    for i in range(len(word)):
        seen = set()
        for j in range(i, len(word)):
            if word[j] not in vowels:
                break
            seen.add(word[j])
            if len(seen) == 5:
                count += 1
    return count

JavaScript

var countVowelSubstrings = function(word) {
    var V = "aeiou", count = 0;
    for (var i = 0; i < word.length; i++) {
        var seen = {}, distinct = 0;
        for (var j = i; j < word.length; j++) {
            var c = word.charAt(j);
            if (V.indexOf(c) === -1) break;
            if (!seen[c]) { seen[c] = true; distinct++; }
            if (distinct === 5) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue