Count substrings that use only vowels and contain all five: Frontier Interview's solution

Question: Count substrings that use only vowels and contain all five

Companies: Snowflake

Difficulty: Medium

Problem statement

Given a string s of lowercase English letters, return the number of contiguous substrings that satisfy both rules:

Every character of the substring is a vowel (a, e, i, o, u).
The substring contains each of the five vowels at least once.

Substrings are counted by position: two equal substrings that start at different indices both count.

Implement:

def count_vowel_substrings(s: str) -> int: ...

Constraints

0 <= len(s) <= 10^5
s contains only lowercase English letters.
The answer can exceed 32 bits.

Start with a working solution, then aim for linear time.

Example 1

Input:  s = "aaeiou"
Output: 2

The valid substrings are "aaeiou" and "aeiou".

Example 2

Input:  s = "aeioxuaei"
Output: 0

The x splits the vowels into "aeio" and "uaei", and neither part contains all five vowels.

Approach

A valid substring has two properties: every character in it is a vowel, and
all five vowels appear in it. The first property splits the string into
vowel runs. A consonant ends every run, so no valid substring crosses
one. Each run is solved on its own and the counts are added.

Brute force. Try every start i. Extend j to the right while s[j]
is a vowel, adding s[j] to a set. Each time the set has five letters,
count one. Stop at the first consonant. This is O(n^2) in the worst case
(a string of only vowels) and is a fine first answer for short inputs. Say
so, then improve it.

Optimal: count by right end. Fix the right end r of a substring
inside a run that starts at start. A left end l gives a valid substring
when s[l..r] holds each vowel at least once. Keep last[v], the latest
index of vowel v inside the current run. The substring s[l..r] contains
v exactly when l <= last[v]. So it contains all five when
l <= min(last.values()). The valid left ends are start .. min(last),
which is min(last) - start + 1 choices. Add that for every r.

Invariants while scanning:

start is the index of the first character of the current vowel run.
last holds only indices from the current run. It is cleared at every
consonant.
Until all five vowels are in last, r adds nothing.

Each character is handled once, with a min over five values, so the scan
is linear.

An equivalent method is the "at most k" sliding window:
exactly_all_five = at_most(5) - at_most(4) over distinct vowels in a
window that also breaks on consonants. It is good to mention, but the
last-seen version is shorter and has fewer off-by-one traps.

Code

VOWELS = frozenset("aeiou")


def count_vowel_substrings_brute(s: str) -> int:
    """O(n^2) reference: extend every start until a consonant."""
    n = len(s)
    total = 0
    for i in range(n):
        seen: set[str] = set()
        for j in range(i, n):
            if s[j] not in VOWELS:
                break
            seen.add(s[j])
            if len(seen) == 5:
                total += 1
    return total


def count_vowel_substrings(s: str) -> int:
    """Count substrings made only of vowels that contain all five vowels.

    For each right end r in a vowel run starting at `start`, the valid left
    ends are start .. min(last seen index of each vowel).
    """
    total = 0
    start = 0
    last: dict[str, int] = {}
    for r, ch in enumerate(s):
        if ch not in VOWELS:
            start = r + 1
            last.clear()
            continue
        last[ch] = r
        if len(last) == 5:
            total += min(last.values()) - start + 1
    return total


if __name__ == "__main__":
    cases = [
        ("", 0),
        ("aeiou", 1),
        ("aeio", 0),
        ("aaeiou", 2),
        ("aeiouu", 2),
        ("uaieuoua", 7),
        ("aeioxuaei", 0),
        ("xaeiouy", 1),
        ("aeiouaeiou", 21),
        ("bcdfg", 0),
    ]
    for text, expected in cases:
        assert count_vowel_substrings(text) == expected, (text, expected)
        assert count_vowel_substrings_brute(text) == expected, (text, expected)

    import random
    for _ in range(2000):
        text = "".join(random.choice("aeioub") for _ in range(random.randint(0, 30)))
        assert count_vowel_substrings(text) == count_vowel_substrings_brute(text), text
    print("ok")

Complexity

Optimal: O(n) time. Each character is visited once and min runs over
at most five values. O(1) extra space: last never holds more than five
keys.
Brute force: O(n^2) time in the worst case (all vowels), O(1) extra
space (the set holds at most five letters).

Test cases

"" → 0 (empty string).
"bcdfg" → 0 (no vowels).
"aeio" → 0 (missing u).
"aeiou" → 1 (the whole string only).
"aaeiou" → 2 ("aaeiou", "aeiou").
"aeiouu" → 2 ("aeiou", "aeiouu").
"uaieuoua" → 7 (overlapping windows with repeats).
"aeioxuaei" → 0 (the consonant splits the vowels into two runs, and
neither run has all five).
"xaeiouy" → 1 (consonants at both ends).
"aeiouaeiou" → 21 (right ends at indices 4..9 add 1, 2, 3, 4, 5, 6).
A string of 10^5 vowels must finish in linear time; the answer can be
near n^2/2, so the count needs a big integer in languages with fixed-size
ints (use long/int64).

Follow-ups

Exactly k distinct vowels, or a custom required set. Replace the
constant 5 with the size of the required set and track last only for
those letters; letters outside the set that are still allowed just
extend the run. For "exactly k distinct", use at_most(k) - at_most(k-1)
with a two-pointer window that resets on consonants.
Return the shortest (or longest) valid substring. Longest: inside
each run that holds all five vowels, the whole run is the answer for
that run. Shortest: at each r with all five seen, the candidate is
s[min(last)..r]; keep the minimum length. Still O(n).
Allow up to k consonants inside the substring. Runs no longer
split the string. Use a sliding window that tracks consonant count and
vowel counts; for each r, the valid left ends form a contiguous range
[lo, hi], where lo is the smallest left end with at most k
consonants and hi is min(last[v]). Maintain lo with a second
pointer. Still O(n).
Streaming input. The last-seen scan already reads one character at a
time with O(1) state (start, last, running total), so it works on a
stream or a file too large for memory. Track start as a position
counter rather than an index into a buffer.
Many range queries count(s[a..b]). Precompute for each r the run
start st(r), f(r) = min(last) (or -1 if not all five seen) and the
full-string contribution c(r) = max(0, f(r) - st(r) + 1), with prefix
sums of c and of f. For a query, right ends in later runs (where
st(r) >= a) contribute c(r), a prefix-sum difference. Right ends in
the run that contains a contribute max(0, f(r) - a + 1); f never
decreases inside a run, so binary search the first r with f(r) >= a
and finish with the prefix sums of f. O(n) preprocessing, O(log n) per
query.

Interviewer expectations

Mid-level (L4)

Restates the rules correctly: only vowels, all five present, overlapping
and repeated occurrences counted separately.
Writes the O(n^2) brute force with early break on a consonant and gets it
right.
Moves to a linear solution with some hints and tests it on a small
example by hand.

Senior (L5)

Sees on their own that consonants split the problem into independent
runs.
Derives the "count left ends per right end" formula, explains why
min(last) - start + 1 is correct, and states the invariants.
Lists the edge cases (empty, no vowels, run without all five, consonants
at the ends) and notes overflow of the count in fixed-width languages.

Staff (L6+)

Finishes the core quickly and generalizes cleanly: arbitrary required
set, exactly-k via at-most differences, consonant budget.
Compares the last-seen method with the at-most sliding window and picks
one with a reason (fewer moving parts, fewer off-by-one risks).
Handles the streaming and range-query extensions, with the right
complexity and a clear plan for testing (brute-force cross-check on
random strings).