Watch 10 video solutions for Longest Substring Of All Vowels in Order, a medium level problem involving String, Sliding Window. This walkthrough by Nalin Goyal has 1,761 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A string is considered beautiful if it satisfies the following conditions:
'a', 'e', 'i', 'o', 'u') must appear at least once in it.'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 * 105word consists of characters 'a', 'e', 'i', 'o', and 'u'.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 | 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. |