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.
The sliding window approach can be used to efficiently find the longest substring that contains all vowels in order.
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.
Time Complexity: O(n)
Space Complexity: O(1)
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.
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) Space Complexity: O(1) |
| Dynamic Programming Approach | Time Complexity: O(n) Space Complexity: O(n) |
| 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. |
Longest Substring Of All Vowels in Order • Nalin Goyal • 1,761 views views
Watch 9 more video solutions →Practice Longest Substring Of All Vowels in Order with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor