LeetCode Solutions Blog

Longest Substring Of All Vowels in Order

Number: 1967

Difficulty: Medium

Paid? No

Problem Description

Given a string composed solely of English vowels, a substring is considered beautiful if it contains all 5 vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) at least once and they appear in alphabetical order (i.e., all ‘a’s come before any ‘e’s, etc.). The task is to determine the length of the longest contiguous beautiful substring within the string. If no such substring exists, return 0.

Key Insights

The substring must include the vowels in the specific order: a, e, i, o, u.
A sliding window or two-pointer approach can efficiently traverse the string.
If there is any violation of the order, reset the tracking and possibly start a new substring from the current character.
Ensure that the substring actually contains all vowels before updating the maximum length.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as each character is processed once.
Space Complexity: O(1), using only constant extra space for tracking variables and states.

Solution

The solution involves iterating through the string while maintaining the current substring's length, the current expected vowel (tracked by an index for "aeiou"), and a flag array to indicate if each vowel has been encountered at least once. When a character violates the current order, check if the substring so far is beautiful and then either reset the state (or possibly start with the current character if it’s 'a'). Update the maximum length accordingly.

Code Solutions

# Python solution with detailed comments
def longest_beautiful_substring(word: str) -> int:
    max_length = 0           # Maximum length of valid beautiful substring found
    current_length = 0       # Current running length of the substring being evaluated
    current_vowel_index = 0  # Tracks the current expected vowel index in "aeiou"
    
    vowels = "aeiou"
    seen = [False] * 5       # Marks if each vowel has been seen in the current substring
    
    for char in word:
        if current_length == 0:
            # Start a new substring only if it begins with 'a'
            if char == 'a':
                current_length = 1
                current_vowel_index = 0
                seen = [True] + [False] * 4
            continue
        
        if char == vowels[current_vowel_index]:
            # Same vowel as expected; extend current substring
            current_length += 1
            seen[current_vowel_index] = True
        elif current_vowel_index < 4 and char == vowels[current_vowel_index + 1]:
            # Character is the next expected vowel; update state accordingly
            current_vowel_index += 1
            current_length += 1
            seen[current_vowel_index] = True
        else:
            # Order is broken; if current substring is beautiful update max_length
            if all(seen):
                max_length = max(max_length, current_length)
            # Reset state: start a new substring if current char is 'a'
            if char == 'a':
                current_length = 1
                current_vowel_index = 0
                seen = [True] + [False] * 4
            else:
                current_length = 0
                current_vowel_index = 0
                seen = [False] * 5
                
    # Final check at end of string in case substring continues till end
    if current_length > 0 and all(seen):
        max_length = max(max_length, current_length)
    
    return max_length

# Example usage:
print(longest_beautiful_substring("aeiaaioaaaaeiiiiouuuooaauuaeiu"))
print(longest_beautiful_substring("aeeeiiiioooauuuaeiou"))