Longest Substring of All Vowels in Order

Medium
1029.

Longest Substring of All Vowels in Order

Longest Substring of All Vowels in Order is a medium coding problem on strings and sliding window, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var longestBeautifulSubstring = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Substring of All Vowels in Order — Solution

Longest Substring of All Vowels in Order solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Substring of All Vowels in Order is a medium coding problem on strings and sliding window, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Strings, Sliding Window
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Longest Substring of All Vowels in Order

  1. Hint 1

    A beautiful substring is a run where each character either repeats the previous vowel or advances to the next one in aeiou.

  2. Hint 2

    Track the current run length and how many distinct vowels it has covered.

  3. Hint 3

    Any break — a consonant, or a vowel that goes backwards — restarts the run, and it can only restart at an a.

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

Java

public static int longestBeautifulSubstring(String word) {
    String order = "aeiou";
    int best = 0, run = 0, distinct = 0;
    char prev = 0;
    for (int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        if (order.indexOf(c) < 0) { run = 0; distinct = 0; prev = 0; continue; }
        if (prev == 0) {
            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 = 0; continue;
        }
        prev = c;
        if (distinct == 5) best = Math.max(best, run);
    }
    return best;
}

C++

int longestBeautifulSubstring(string word) {
    string order = "aeiou";
    int best = 0, run = 0, distinct = 0;
    char prev = 0;
    for (char c : word) {
        if (order.find(c) == string::npos) { run = 0; distinct = 0; prev = 0; continue; }
        if (prev == 0) {
            if (c != 'a') continue;
            run = 1; distinct = 1;
        } else if (c == prev) {
            run++;
        } else if ((int) order.find(c) == (int) order.find(prev) + 1) {
            run++; distinct++;
        } else if (c == 'a') {
            run = 1; distinct = 1;
        } else {
            run = 0; distinct = 0; prev = 0; 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Sliding Window Technique