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^5word consists of lowercase English letters.
Hints for Longest Substring of All Vowels in Order
Hint 1
A beautiful substring is a run where each character either repeats the previous vowel or advances to the next one in
aeiou.Hint 2
Track the current run length and how many distinct vowels it has covered.
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
- For each character, if it is not a vowel, reset the run.
- If the run is empty, start it only on an
'a'. - Otherwise extend on an equal vowel, or on the next vowel in
aeiou(incrementing the distinct count). - On any other vowel, restart — at 1 if the character is
'a', at 0 otherwise. - 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 bestJava
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