Count vowel-only substrings with all vowels
Company: Expedia
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a lowercase English string s, return the number of contiguous substrings that
(
1) consist only of vowels from the set {a, e, i, o, u}, and
(
2) contain each of the five vowels at least once. Constraints: 1 <= |s| <= 200000. Design an O(n) time solution using a sliding-window/two-pointer approach with O(
1) extra space. Explain how you handle consonants that break windows, repeated vowels, and long runs of vowels. Provide code and analyze time and space complexity.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Count vowel-only substrings with all vowels states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given a lowercase English string `s`, return the number of contiguous substrings that satisfy BOTH conditions:
1. The substring consists **only** of vowels from the set `{a, e, i, o, u}` (no consonants).
2. The substring contains **each** of the five vowels at least once.
A consonant anywhere inside a candidate substring disqualifies it, so consonants act as hard breaks that split `s` into maximal vowel-only segments. Within each such segment you count the substrings that include all five vowels.
**Example 1**
Input: `s = "aeiou"`
Output: `1`
The only valid substring is `"aeiou"` itself.
**Example 2**
Input: `s = "aeiouu"`
Output: `2`
Valid substrings: `"aeiou"` and `"aeiouu"`.
**Example 3**
Input: `s = "aeioub"`
Output: `1`
The trailing consonant `b` cannot be part of any valid substring; only `"aeiou"` qualifies.
Constraints:
- `1 <= |s| <= 200000`
- `s` contains only lowercase English letters.
- Aim for O(n) time using a sliding window / two-pointer approach with O(1) extra space (the vowel-count table is fixed size 5).
Constraints
- 1 <= |s| <= 200000
- s contains only lowercase English letters
- Consonants split s into maximal vowel-only segments; only vowel-only substrings can qualify
- A valid substring must contain each of a, e, i, o, u at least once
- Target: O(n) time, O(1) extra space
Examples
Input: "aeiou"
Expected Output: 1
Explanation: Only the whole string contains all five vowels.
Input: "aeiouu"
Expected Output: 2
Explanation: Valid substrings are 'aeiou' (chars 0-4) and 'aeiouu' (chars 0-5).
Hints
- Consonants can never appear in a valid substring, so first split s into maximal runs of vowels and solve each run independently.
- Within one vowel run, for a fixed right end, count the number of valid left starts. As right moves forward, the smallest valid left only moves forward too (monotonic) — that is the two-pointer invariant.
- Track how many DISTINCT vowels the current window has using a size-5 frequency table. While all 5 are present, advance left as far as possible; the count of valid starts for this right is (left - segmentStart).
- Use a 64-bit accumulator: with up to 200000 characters the answer can exceed 32-bit range.