Longest Substring Of All Vowels in Order

LeetCode 1839: Longest Substring Of All Vowels in Order asks you to find the length of the longest "beautiful" substring inside a string that only contains vowels. A substring is "beautiful" if it contains all five vowels (a, e, i, o, u) exactly in non-decreasing order, and each vowel appears at least once.

For example, given "aeiaaioaaaaeiiiiouuuooaauuaeiu", the answer is 13, because the substring "aaaaeiiiiouuu" is the longest beautiful one.

What makes a substring "beautiful"

The rules are specific. A beautiful substring must:

1. Contain all five vowels: a, e, i, o, u.
2. Have them in non-decreasing order. So 'a' can repeat, then 'e' can repeat, then 'i', and so on. But you can never go backwards (like 'o' followed by 'i').
3. Each vowel must appear at least once. A string like "aeiou" is beautiful. A string like "aiiou" is not, because 'e' is missing.

This means you are looking for contiguous runs where the characters never decrease in the vowel ordering, and by the time the run ends, all five vowels have shown up.

The key insight: scan and track groups

You do not need a sliding window with two independent pointers here. Instead, you can scan left to right and maintain a single running candidate substring. At each position, you ask: does this character continue the current candidate, or does it break it?

There are three cases for the character at position i:

• Same or larger vowel (s[i] >= s[i-1]): extend the current candidate. If this is a new vowel we have not seen yet in this candidate, increment the distinct vowel count.
• It is 'a' and it is smaller than the previous character: the current candidate is broken, but 'a' starts a fresh one. Reset the start position and the distinct count to 1.
• It is not 'a' and it is smaller: the candidate is broken and nothing useful starts here. Clear everything and wait for the next 'a'.

Whenever the distinct vowel count hits 5, you have a beautiful substring. Update the max length.

This is a single pass through the string. No nested loops, no hash maps. Just a pointer and a counter.

Walking through it step by step

Let's trace through the string "aeiaaioaaaaeiiiiouuuooaauuaeiu". At each step, we track the current candidate substring, the set of distinct vowels it contains, and the best length found so far.

The longest beautiful substring is "aaaaeiiiiouuu" starting at index 7, with length 13. It contains groups of a's, then e's, then i's, then o, then u's, all five vowels in order.

The code

Here is the complete solution in Python:

def longest_beautiful_substring(word: str) -> int:
    if len(word) < 5:
        return 0

    best = 0
    current_len = 1
    distinct = 1

    for i in range(1, len(word)):
        if word[i] >= word[i - 1]:
            current_len += 1
            if word[i] != word[i - 1]:
                distinct += 1
        elif word[i] == 'a':
            current_len = 1
            distinct = 1
        else:
            current_len = 0
            distinct = 0

        if distinct == 5:
            best = max(best, current_len)

    return best

Let's break down each piece:

1. Early exit. If the string has fewer than 5 characters, no beautiful substring can exist.
2. Tracking variables. current_len is the length of the current candidate. distinct counts how many unique vowels have appeared in it.
3. Extend case. If the current character is greater than or equal to the previous one, the candidate grows. If it is a new vowel (different from the previous), bump distinct.
4. Reset to 'a'. If the current character is 'a' but less than the previous, we broke the non-decreasing order. But 'a' can start a fresh candidate.
5. Full break. If the character is smaller than the previous and not 'a', no candidate can start here. Set both counters to 0.
6. Check for beautiful. Whenever distinct reaches 5, all vowels are present and in order. Update best.

Complexity analysis

Time: O(n). One pass through the string. Each character is visited exactly once. All operations per character are O(1).

Space: O(1). Only a few integer variables. No extra data structures.

The building blocks

This problem decomposes into two reusable pieces that show up in many string problems:

1. Non-decreasing group tracking

The core mechanic: scan left to right and extend a group as long as the next character is greater than or equal to the current one. When the order breaks, decide whether to reset or skip.

if word[i] >= word[i - 1]:
    current_len += 1
elif word[i] == 'a':
    current_len = 1
else:
    current_len = 0

This pattern appears in problems like counting homogenous substrings, finding the longest increasing run, and any problem where you need to track contiguous monotonic segments. The shape of the transition logic (extend, restart, or skip) changes, but the single-pass scan with a running counter stays the same.

2. Distinct element counting within a window

Tracking how many unique values have appeared in the current candidate:

if word[i] != word[i - 1]:
    distinct += 1

Because the string is constrained to vowels in order, you do not need a set or a hash map. A simple integer counter works. But the idea of "count distinct elements to check a condition" appears in sliding window problems like Longest Substring with At Most K Distinct Characters, Fruit Into Baskets, and Subarrays with K Different Integers. In those problems you use a dict. Here the constraint is tighter, so a counter suffices.

These two pieces combine cleanly. The group tracker tells you when to extend or reset. The distinct counter tells you when a candidate qualifies as beautiful. Neither piece is complex on its own, and learning them independently means you can snap them together when a new problem asks for "the longest contiguous segment satisfying some completeness condition."

Edge cases

Before submitting, verify your solution handles:

• String shorter than 5 characters like "aei": return 0. You need all 5 vowels, so the string must be at least length 5.
• Exact beautiful string "aeiou": return 5. The minimum possible beautiful substring.
• All identical vowels "aaaa": return 0. Only one distinct vowel, never reaches 5.
• Multiple beautiful substrings "aeiouaeiou": the break between the two occurs at the second 'a'. Each substring has length 5. Return 5.
• Beautiful substring at the very end "uuuaeiou": the first few characters cannot form a candidate (start with 'u'). The candidate starting at the 'a' at index 3 reaches length 5 by the end.
• Long runs of single vowels "aaaaaeeeeeiiiiiooooouuuuu": return 25. One giant beautiful substring.

From understanding to recall

You have seen the pattern: scan left to right, extend while non-decreasing, track distinct vowels, check for all five. The logic is compact and the code is short. But reproducing it under pressure is a different story.

The details that trip people up are small. Do you reset distinct to 1 or 0 when restarting at 'a'? Do you reset current_len to 0 or 1 when the candidate breaks on a non-'a' character? What happens when the character equals the previous one? These are not conceptual problems. They are recall problems, and they cost time in interviews.

Spaced repetition closes that gap. You practice writing the group-tracking scan and the distinct-element check from memory at increasing intervals. After a few rounds, the transition logic is automatic. You see "longest contiguous segment with all required elements" in a problem statement, and the code flows out without hesitation.

Related posts

• Longest Substring Without Repeating Characters - Another single-pass string problem, using a sliding window with a set instead of group tracking
• Valid Anagram - Introduces frequency counting, the simpler cousin of the distinct-element tracking used here
• Sliding Window Pattern - The general pattern guide for problems involving contiguous subarray or substring conditions