1839. Longest Substring Of All Vowels in Order
Asked at Rippling
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
String
Companies
1
Problem
You are given a string word that contains only the five English vowels: a, e, i, o, u.
A substring is called beautiful when it meets two rules. First, it must contain all five vowels at least once. Second, its letters must be in alphabetical order: every a comes before every e, every e before every i, and so on up to u. So a beautiful substring looks like a block of as, then a block of es, then is, then os, then us.
Return the length of the longest beautiful substring of word. If no beautiful substring exists, return 0. Remember that a substring must be a contiguous piece of the string — you cannot skip characters.
Constraints
- ●
1 <= word.length <= 5 * 10^5 - ●
word consists of characters 'a', 'e', 'i', 'o', and 'u' only
Examples
word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"13word = "aeeeiiiioooauuuaeiou"5word = "a"0Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Rippling | Medium | View all Rippling questions → |
How to Think About It
The valid substring must contain all 5 vowels (a, e, i, o, u) in alphabetical order. That means the substring starts with some a's, then e's, then i's, then o's, then u's.
Use a sliding window [left, right]. Track whether each vowel has been seen. The window is valid when all 5 vowels are present AND in order.
Key insight: instead of checking order every time, track the "phase" of the window. The window transitions through phases: a -> e -> i -> o -> u. When a vowel breaks the order, you need to shrink the window.
Simpler approach: use a sliding window with a hash map counting vowels. When all 5 vowels are present, check if they're in order (the count of a's should be at the start, then e's, etc.). Actually, just track the last occurrence of each vowel and verify the order constraint.
Even simpler: for each position, try to extend the window to the right. Track the last position where each vowel was seen. The window is valid if last_a < last_e < last_i < last_o < last_u. Update max length.
Optimal Approach
Two-pointer approach:
Step 1: Maintain a window [left, right] and a hash map of last positions for each vowel.
Step 2: Expand right. Update last_positions[word[right]] = right.
Step 3: When all 5 vowels are in the map, check if they're in order: last_a < last_e < last_i < last_o < last_u.
Step 4: If in order, update max length = max(max, right - left + 1).
Step 5: If not in order, shrink left (increment left past the earliest out-of-order vowel).
Alternative greedy approach: track the last position of each vowel. The window is valid when all 5 are present and sorted by position. The left boundary is max(last_a, last_e, last_i, last_o, last_u) + 1 when order is broken... Actually, the simplest: use a sliding window that tracks counts. When all 5 vowels have count > 0, check if the order is correct.
Time: O(n) -- each character visited once. Space: O(1) -- fixed 5 vowels.
Sliding window with vowel counts
What Trips People Up in Real Interviews
Confusing "in alphabetical order" with "in any order." The vowels must appear as a, e, i, o, u in the substring, not just all present.
Trying to use a fixed pattern match. The substring can have varying numbers of each vowel (e.g., "aaeeiioouu" is valid, "aeiou" is valid, "aaaeiiioouuu" is valid).
Not handling the case where the string doesn't contain all 5 vowels. If a vowel never appears, the answer is 0.
Using a hash map to store all characters instead of just tracking vowel counts. Since the string only contains vowels, you only need counts for a, e, i, o, u.
Forgetting that the window might need to shrink from the left. When a vowel appears out of order, you may need to move the left pointer to restore the ordering constraint.
Solution Code
O(n) timedef longestBeautifulSubstring(word):
vowels = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}
left = 0
count = [0] * 5
max_len = 0
for right in range(len(word)):
count[vowels[word[right]]] += 1
while left <= right and count[vowels[word[right]]] > 0 and not all(count):
left += 1
if all(count):
max_len = max(max_len, right - left + 1)
return max_lenFrequently Asked Questions
What is the Longest Substring Of All Vowels in Order problem?
Given a string word consisting only of vowels "aeiou", return the length of the longest substring that contains every vowel at least once in alphabetical order. This is a sliding window problem with a specific ordering constraint.
How do you solve Longest Substring Of All Vowels in Order?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Longest Substring Of All Vowels in Order?
Longest Substring Of All Vowels in Order is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Longest Substring Of All Vowels in Order?
- Confusing "in alphabetical order" with "in any order." The vowels must appear as a, e, i, o, u in the substring, not just all present.
- Trying to use a fixed pattern match. The substring can have varying numbers of each vowel (e.g., "aaeeiioouu" is valid, "aeiou" is valid, "aaaeiiioouuu" is valid).
- Not handling the case where the string doesn't contain all 5 vowels. If a vowel never appears, the answer is 0.
- Using a `hash map` to store all characters instead of just tracking vowel counts. Since the string only contains vowels, you only need counts for a, e, i, o, u.
- Forgetting that the window might need to shrink from the left. When a vowel appears out of order, you may need to move the left pointer to restore the ordering constraint.