Longest Substring Of All Vowels in Order

Problem Description

Given a string consisting of English vowels, return the length of the longest substring that contains each of the 5 vowels ('a', 'e', 'i', 'o', 'u') at least once and sorted in alphabetical order. If no such substring exists, return 0.

Key Insights

• A valid substring must include all 5 vowels at least once.
• The vowels must appear in the order: 'a', 'e', 'i', 'o', 'u'.
• We can utilize a sliding window approach to efficiently find the longest valid substring.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string, since we are iterating through the string once. Space Complexity: O(1), as we only need a fixed number of variables for tracking the state.

Solution

To find the longest beautiful substring, we will use a sliding window approach:

1. Initialize two pointers, start and end, to represent the current window of consideration.
2. Use a dictionary or array to count the occurrences of each vowel within the current window.
3. Expand the end pointer to include characters until we have at least one of each vowel.
4. Once we have all vowels, check if the substring is in the correct order. If it is, update the maximum length.
5. Move the start pointer to shrink the window while maintaining the condition of having all vowels.
6. Repeat until the end pointer reaches the end of the string.

Code Solutions