Longest Substring Of All Vowels in Order
Asked at Rippling
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.
Asked At
| 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.
Visual walkthrough for "aeeaeeiiiouuuaeiou":
Expand right, tracking the current expected vowel phase:
Phase 0 (a): accumulate a's
Phase 1 (e): when first e appears, switch to phase 1
Phase 2 (i): when first i appears, switch to phase 2
Phase 3 (o): when first o appears, switch to phase 3
Phase 4 (u): when first u appears, switch to phase 4
If an earlier vowel appears while in a later phase, we need to restart.
Actually, simpler approach: just expand the window and check if it contains all 5 vowels in order. Use two pointers and maintain a count of each vowel.
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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.