Longest Substring Of All Vowels in Order - Solution & Explanation
Problem Statement
A string is considered beautiful if it satisfies the following conditions:
- Each of the 5 English vowels (
'a','e','i','o','u') must appear at least once in it. - The letters must be sorted in alphabetical order (i.e. all
'a's before'e's, all'e's before'i's, etc.).
For example, strings "aeiou" and "aaaaaaeiiiioou" are considered beautiful, but "uaeio", "aeoiu", and "aaaeeeooo" are not beautiful.
Given a string word consisting of English vowels, return the length of the longest beautiful substring of word. If no such substring exists, return 0.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu" Output: 13 Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.
Example 2:
Input: word = "aeeeiiiioooauuuaeiou" Output: 5 Explanation: The longest beautiful substring in word is "aeiou" of length 5.
Example 3:
Input: word = "a" Output: 0 Explanation: There is no beautiful substring, so return 0.
Constraints:
1 <= word.length <= 5 * 105wordconsists of characters'a','e','i','o', and'u'.
Approach Overview
Problem Overview: You receive a string and need the length of the longest substring where vowels appear in strictly non-decreasing alphabetical order: a → e → i → o → u. The substring must contain all five vowels at least once and maintain this order throughout.
Approach 1: Sliding Window Scan (O(n) time, O(1) space)
This problem fits naturally with a sliding window style scan. Iterate through the string once while tracking the current valid vowel sequence. If the current character maintains alphabetical order relative to the previous one, extend the window. If the order breaks (for example i → a), reset the window starting from the current character. Maintain a counter for how many distinct vowels have appeared in sequence. Whenever the sequence includes all five vowels, update the maximum substring length. This works because a valid substring is always contiguous and the vowel ordering constraint only depends on adjacent characters.
Approach 2: Dynamic Programming with Vowel Stages (O(n) time, O(1) space)
The problem can also be modeled as stages of vowel progression using dynamic programming. Track the longest valid sequence ending at each vowel stage (a, e, i, o, u). When processing a character, update the stage corresponding to that vowel: continuing the same stage if repeated or transitioning from the previous stage if the order advances. For example, an e can extend an existing e sequence or transition from an a sequence. Once the u stage grows, update the answer. This method formalizes the ordering constraint but requires more bookkeeping than the sliding window.
Both methods rely heavily on sequential character processing, which is typical for string problems where order matters but backtracking is unnecessary.
Recommended for interviews: The sliding window approach is usually what interviewers expect. It demonstrates that you recognize the ordered constraint and can track contiguous segments efficiently in a single pass. Mentioning the dynamic programming variant shows deeper algorithmic thinking, but the O(n) sliding scan is simpler and easier to implement under time pressure.
Approach 1: Sliding Window Approach
The sliding window approach can be used to efficiently find the longest substring that contains all vowels in order.
- Initialize two pointers to maintain the sliding window boundaries.
- Iterate over the string with these two pointers to identify valid substrings.
- Keep track of encountered vowels and ensure they appear in the correct order.
- When the sequence breaks, adjust the window accordingly.
The C implementation uses a loop that iterates through the given string with an array of vowels to verify that all vowels are present in order within the substring. As each vowel is encountered consecutively in order, the length of the substring increments. If the substring is beautiful, it updates the maximum length.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Dynamic Programming Approach
Utilizing dynamic programming can also assist in achieving an efficient solution to identify the longest beautiful substring. The premise involves storing intermediate results to make decisions on forming a valid substring based on past computations.
This method, however, can be more complex and may require additional data structures compared to the sliding window approach.
This C implementation uses a 2D array to store results for each character in the input string, at each step comparing the progress towards completing a beautiful substring. It keeps track of these to determine the longest length possible.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Two Pointers + Simulation
We can first transform the string word. For example, for word="aaaeiouu", we can transform it into data items ('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2) and store them in an array arr. Each data item's first element represents a vowel, and the second element represents the number of times the vowel appears consecutively. This transformation can be implemented using two pointers.
Next, we traverse the array arr, each time taking 5 adjacent data items, and judge whether the vowels in these data items are 'a', 'e', 'i', 'o', 'u' respectively. If so, calculate the total number of times the vowels appear in these 5 data items, which is the length of the current beautiful substring, and update the maximum value of the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string word.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) Space Complexity: O(1) |
| Dynamic Programming Approach | Time Complexity: O(n) Space Complexity: O(n) |
| Two Pointers + Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Scan | O(n) | O(1) | Best general solution. Single pass with minimal state tracking. |
| Dynamic Programming (Vowel Stages) | O(n) | O(1) | Useful when modeling ordered transitions between character groups. |
Video Solution
Longest Substring Of All Vowels in Order • Nalin Goyal • 1,765 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Longest Substring Of All Vowels in Order easy or hard?
Longest Substring Of All Vowels in Order Python/Java solution
How to solve Longest Substring Of All Vowels in Order in O(n)?
What is the best approach for Longest Substring Of All Vowels in Order?
Is Longest Substring Of All Vowels in Order asked at Google/Amazon/Meta?
What data structure is used in Longest Substring Of All Vowels in Order?
What is the time complexity of Longest Substring Of All Vowels in Order?
Ready to solve this problem?
Practice Longest Substring Of All Vowels in Order with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor