Longest Substring of All Vowels in Order — Medium Problem & Solution

Problem statement

A string is beautiful when it contains all five vowels at least once and its characters appear in alphabetical vowel order — every a before every e, every e before every i, and so on.

Return the length of the longest beautiful substring of word, or 0 if there is none.

Example 1

Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
Output: 13
Explanation: The substring `aaaaeiiiiouuu`.

Example 2

Input: word = "aeeeiiiioooauuuaeiou"
Output: 5
Explanation: The trailing `aeiou`.

Example 3

Input: word = "codekairo"
Output: 0
Explanation: Consonants break every run, and no run reaches all five vowels.

Constraints

• 1 <= word.length <= 5 * 10^5
• word consists of lowercase English letters.

How to solve Longest Substring of All Vowels in Order

Sweep once, carrying the current run's length and the number of distinct vowels it has covered. Extend on a repeat or on the next vowel in order; restart otherwise. Whenever the distinct count hits 5, the current run is beautiful, so record its length.

Approach

1. For each character, if it is not a vowel, reset the run.
2. If the run is empty, start it only on an 'a'.
3. Otherwise extend on an equal vowel, or on the next vowel in aeiou (incrementing the distinct count).
4. On any other vowel, restart — at 1 if the character is 'a', at 0 otherwise.
5. Track the maximum run length seen while the distinct count is 5.

Why it works

The ordering constraint means a beautiful substring can never restart in the middle — the moment a vowel goes backwards, everything before it is unusable, and the only valid fresh start is an 'a'. That is what lets a single pass with two counters replace a window that would otherwise have to shrink from the left.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• A run may only begin at 'a'; starting mid-sequence would miss the leading vowels.
• A backwards step to 'a' restarts the run at that character, not at zero.
• The answer is 0 when no run ever covers all five vowels — not the longest partial run.

Reference solution

Python

def longestBeautifulSubstring(word: str) -> int:
    order = "aeiou"
    best = run = distinct = 0
    prev = ""
    for c in word:
        if c not in order:
            run = distinct = 0
            prev = ""
            continue
        if prev == "":
            if c != "a":
                continue
            run, distinct = 1, 1
        elif c == prev:
            run += 1
        elif order.index(c) == order.index(prev) + 1:
            run += 1
            distinct += 1
        elif c == "a":
            run, distinct = 1, 1
        else:
            run = distinct = 0
            prev = ""
            continue
        prev = c
        if distinct == 5:
            best = max(best, run)
    return best

JavaScript

var longestBeautifulSubstring = function(word) {
    var order = "aeiou";
    var best = 0, run = 0, distinct = 0, prev = "";
    for (var i = 0; i < word.length; i++) {
        var c = word.charAt(i);
        if (order.indexOf(c) === -1) { run = 0; distinct = 0; prev = ""; continue; }
        if (prev === "") {
            if (c !== "a") continue;
            run = 1; distinct = 1;
        } else if (c === prev) {
            run++;
        } else if (order.indexOf(c) === order.indexOf(prev) + 1) {
            run++; distinct++;
        } else if (c === "a") {
            run = 1; distinct = 1;
        } else {
            run = 0; distinct = 0; prev = ""; continue;
        }
        prev = c;
        if (distinct === 5 && run > best) best = run;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium