How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Expedia.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Expedia during technical interviews.

Count vowel-only substrings with all vowels

Quick Overview

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.

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).

Input: "aeioub"

Expected Output: 1

Explanation: The trailing consonant 'b' is excluded; only 'aeiou' qualifies.

Input: "baeiou"

Expected Output: 1

Explanation: The leading consonant breaks the window; only the 'aeiou' suffix qualifies.

Input: "aeio"

Expected Output: 0

Explanation: No 'u' anywhere, so no substring can contain all five vowels.

Input: ""

Expected Output: 0

Explanation: Empty string has no substrings.

Input: "aeiouaeiou"

Expected Output: 21

Explanation: Multiple overlapping windows across the 10-char all-vowel run yield 21 valid substrings.

Input: "xyz"

Expected Output: 0

Explanation: No vowels at all.

Input: "aaaaaeiou"

Expected Output: 5

Explanation: A long run of 'a' before 'eiou'; the 5 valid windows differ only by how many leading 'a's they include.

Input: "aeioubaeiou"

Expected Output: 2

Explanation: The consonant 'b' splits the string into two 'aeiou' segments, each contributing one valid substring.

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.

Quick Overview