Longest Substring Of All Vowels in Order solution and explanation
Google
9 more videos on this problem
Longest Substring Of All Vowels in OrderNalin Goyal · 12:45 · 1K views
Longest Substring Of All Vowels in Order (Leetcode 1839)Coding Interviews · 20:03 · 1K views
1839. Longest Substring Of All Vowels in Order (Leetcode Medium)Programming Live with Larry · 11:13 · 952 views
1839. Longest Substring Of All Vowels in OrderRamkrishna Sharma · 14:38 · 646 views
【每日一题】1839. Longest Substring Of All Vowels in Order, 4/29/2021Huifeng Guan · 20:42 · 303 views
Leetcode 1839. Longest Substring Of All Vowels in Order (list groups)LetsCode · 6:52 · 263 views
Leetcode 1839 Longest Substring Of All Vowels in Order - two-pointer sliding window methodCode-Yao · 12:03 · 229 views
1839. Longest Substring Of All Vowels in OrderLeetcode and Interview Question · 6:31 · 150 views
Practicing LeetCode: 1839 Longest Substring of All Vowels in OrderAlejoWTF · 41:46 · 8 views
LeetCode 1839: Longest Substring Of All Vowels in OrderAlitaCode · 26:41 · 2 views
The problem
A string is considered beautiful if it satisfies the following conditions:
- Each of the 5 English vowels (
'a','e','i','o','u') must appear at least once in it. - The letters must be sorted in alphabetical order (i.e. all
'a's before'e's, all'e's before'i's, etc.).
For example, strings "aeiou" and "aaaaaaeiiiioou" are considered beautiful, but "uaeio", "aeoiu", and "aaaeeeooo" are not beautiful.
Given a string word consisting of English vowels, return the length of the longest beautiful substring of word. If no such substring exists, return 0.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: word = "aeiaaioaaaaeiiiiouuuooaauuaeiu" Output: 13 Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.
Example 2:
Input: word = "aeeeiiiioooauuuaeiou" Output: 5 Explanation: The longest beautiful substring in word is "aeiou" of length 5.
Example 3:
Input: word = "a" Output: 0 Explanation: There is no beautiful substring, so return 0.
Constraints:
1 <= word.length <= 5 * 105wordconsists of characters'a','e','i','o', and'u'.
Approach overview
Problem Overview: You receive a string and need the length of the longest substring where vowels appear in strictly non-decreasing alphabetical order: a → e → i → o → u. The substring must contain all five vowels at least once and maintain this order throughout.
Approach 1: Sliding Window Scan (O(n) time, O(1) space)
This problem fits naturally with a sliding window style scan. Iterate through the string once while tracking the current valid vowel sequence. If the current character maintains alphabetical order relative to the previous one, extend the window. If the order breaks (for example i → a), reset the window starting from the current character. Maintain a counter for how many distinct vowels have appeared in sequence. Whenever the sequence includes all five vowels, update the maximum substring length. This works because a valid substring is always contiguous and the vowel ordering constraint only depends on adjacent characters.
Approach 2: Dynamic Programming with Vowel Stages (O(n) time, O(1) space)
The problem can also be modeled as stages of vowel progression using dynamic programming. Track the longest valid sequence ending at each vowel stage (a, e, i, o, u). When processing a character, update the stage corresponding to that vowel: continuing the same stage if repeated or transitioning from the previous stage if the order advances. For example, an e can extend an existing e sequence or transition from an a sequence. Once the u stage grows, update the answer. This method formalizes the ordering constraint but requires more bookkeeping than the sliding window.
Both methods rely heavily on sequential character processing, which is typical for string problems where order matters but backtracking is unnecessary.
Recommended for interviews: The sliding window approach is usually what interviewers expect. It demonstrates that you recognize the ordered constraint and can track contiguous segments efficiently in a single pass. Mentioning the dynamic programming variant shows deeper algorithmic thinking, but the O(n) sliding scan is simpler and easier to implement under time pressure.
Approach 1: Sliding Window Approach
The sliding window approach can be used to efficiently find the longest substring that contains all vowels in order.
- Initialize two pointers to maintain the sliding window boundaries.
- Iterate over the string with these two pointers to identify valid substrings.
- Keep track of encountered vowels and ensure they appear in the correct order.
- When the sequence breaks, adjust the window accordingly.
def longest_beautiful_substring(word: str) -> int:
vowels = 'aeiou'
max_length, length, vowel_index = 0, 0, 0
for c in word:
if c == vowels[vowel_index]:
length += 1
if vowel_index == 4:
max_length = max(max_length, length)
elif vowel_index < 4 and c == vowels[vowel_index + 1]:
vowel_index += 1
length += 1
if vowel_index == 4:
max_length = max(max_length, length)
elif c == 'a':
length = 1
vowel_index = 0
else:
length = 0
vowel_index = 0
return max_length
print(longest_beautiful_substring("aeiaaioaaaaeiiiiouuuooaauuaeiu")) # Output: 13public class Solution {
public int longestBeautifulSubstring(String word) {
String vowels = "aeiou";
int maxLength = 0, length = 0, vowelIndex = 0;
for (char c : word.toCharArray()) {
if (c == vowels.charAt(vowelIndex)) {
length++;
if (vowelIndex == 4) {
maxLength = Math.max(maxLength, length);
}
} else if (vowelIndex < 4 && c == vowels.charAt(vowelIndex + 1)) {
vowelIndex++;
length++;
if (vowelIndex == 4) {
maxLength = Math.max(maxLength, length);
}
} else if (c == 'a') {
length = 1;
vowelIndex = 0;
} else {
length = 0;
vowelIndex = 0;
}
}
return maxLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13
}
}#include <iostream>
#include <string>
using namespace std;
int longestBeautifulSubstring(string word) {
string vowels = "aeiou";
int maxLength = 0, length = 0, vowelIndex = 0;
for(char c : word) {
if(c == vowels[vowelIndex]) {
length++;
if(vowelIndex == 4) {
maxLength = max(maxLength, length);
}
} else if(vowelIndex < 4 && c == vowels[vowelIndex + 1]) {
vowelIndex++;
length++;
if(vowelIndex == 4) {
maxLength = max(maxLength, length);
}
} else if(c == 'a') {
length = 1;
vowelIndex = 0;
} else {
length = 0;
vowelIndex = 0;
}
}
return maxLength;
}
int main() {
cout << longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu") << endl; // Output: 13
return 0;
}function longestBeautifulSubstring(word) {
let vowels = 'aeiou';
let maxLength = 0, length = 0, vowelIndex = 0;
for (let c of word) {
if (c === vowels[vowelIndex]) {
length++;
if (vowelIndex === 4) {
maxLength = Math.max(maxLength, length);
}
} else if (vowelIndex < 4 && c === vowels[vowelIndex + 1]) {
vowelIndex++;
length++;
if (vowelIndex === 4) {
maxLength = Math.max(maxLength, length);
}
} else if (c === 'a') {
length = 1;
vowelIndex = 0;
} else {
length = 0;
vowelIndex = 0;
}
}
return maxLength;
}
console.log(longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13#include <stdio.h>
#include <string.h>
int longestBeautifulSubstring(char *word) {
int vowels[] = {'a', 'e', 'i', 'o', 'u'};
int maxLength = 0, length = 0, vowelIndex = 0;
int n = strlen(word);
for(int i = 0; i < n; i++) {
if(word[i] == vowels[vowelIndex]) {
length++;
if(vowelIndex == 4) {
maxLength = maxLength > length ? maxLength : length;
}
} else if(vowelIndex < 4 && word[i] == vowels[vowelIndex + 1]) {
vowelIndex++;
length++;
if(vowelIndex == 4) {
maxLength = maxLength > length ? maxLength : length;
}
} else if(word[i] == 'a') {
length = 1;
vowelIndex = 0;
} else {
length = 0;
vowelIndex = 0;
}
}
return maxLength;
}
int main() {
printf("%d\n", longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13
return 0;
}using System;
public class Solution {
public int LongestBeautifulSubstring(string word) {
string vowels = "aeiou";
int maxLength = 0, length = 0, vowelIndex = 0;
foreach (char c in word) {
if (c == vowels[vowelIndex]) {
length++;
if (vowelIndex == 4) {
maxLength = Math.Max(maxLength, length);
}
} else if (vowelIndex < 4 && c == vowels[vowelIndex + 1]) {
vowelIndex++;
length++;
if (vowelIndex == 4) {
maxLength = Math.Max(maxLength, length);
}
} else if (c == 'a') {
length = 1;
vowelIndex = 0;
} else {
length = 0;
vowelIndex = 0;
}
}
return maxLength;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LongestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13
}
}The Python solution uses a similar method by iterating through characters of the given string, ensuring each next character aligns with the order of vowels, and updating the longest beautiful substring length when possible.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Dynamic Programming Approach
Utilizing dynamic programming can also assist in achieving an efficient solution to identify the longest beautiful substring. The premise involves storing intermediate results to make decisions on forming a valid substring based on past computations.
This method, however, can be more complex and may require additional data structures compared to the sliding window approach.
def longest_beautiful_substring(word: str) -> int:
n = len(word)
dp = [[0] * 5 for _ in range(n + 1)]
max_length = 0
for i in range(1, n + 1):
c = word[i - 1]
for j in range(5):
if c == 'aeiou'[j]:
if j == 0:
dp[i][j] = dp[i - 1][j] + 1
elif dp[i - 1][j - 1] > 0:
dp[i][j] = dp[i - 1][j] + 1
if j == 4:
max_length = max(max_length, dp[i][j])
return max_length
print(longest_beautiful_substring("aeiaaioaaaaeiiiiouuuooaauuaeiu")) # Output: 13import java.util.*;
public class Solution {
public int longestBeautifulSubstring(String word) {
int n = word.length();
int[][] dp = new int[n + 1][5];
int maxLength = 0;
for (int i = 1; i <= n; i++) {
char c = word.charAt(i - 1);
for (int j = 0; j < 5; j++) {
if (c == "aeiou".charAt(j)) {
if (j == 0) {
dp[i][j] = dp[i - 1][j] + 1;
} else if (dp[i - 1][j - 1] > 0) {
dp[i][j] = dp[i - 1][j] + 1;
}
}
if (j == 4) { // Complete "aeiou"
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int longestBeautifulSubstring(string word) {
int n = word.size();
vector<vector<int>> dp(n + 1, vector<int>(5, 0));
int maxLength = 0;
for (int i = 1; i <= n; i++) {
char c = word[i - 1];
for (int j = 0; j < 5; j++) {
if (c == "aeiou"[j]) {
if (j == 0) {
dp[i][j] = dp[i - 1][j] + 1;
} else if (dp[i - 1][j - 1] > 0) {
dp[i][j] = dp[i - 1][j] + 1;
}
}
if (j == 4) { // Complete "aeiou"
maxLength = max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
int main() {
cout << longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu") << endl; // Output: 13
return 0;
}function longestBeautifulSubstring(word) {
let n = word.length;
let dp = Array.from({ length: n + 1 }, () => Array(5).fill(0));
let maxLength = 0;
for (let i = 1; i <= n; i++) {
let c = word[i - 1];
for (let j = 0; j < 5; j++) {
if (c === 'aeiou'[j]) {
if (j === 0) {
dp[i][j] = dp[i - 1][j] + 1;
} else if (dp[i - 1][j - 1] > 0) {
dp[i][j] = dp[i - 1][j] + 1;
}
}
if (j === 4) {
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
console.log(longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13#include <stdio.h>
#include <string.h>
int longestBeautifulSubstring(char *word) {
int n = strlen(word);
int dp[n + 1][5];
memset(dp, 0, sizeof(dp));
int maxLength = 0;
for (int i = 1; i <= n; i++) {
char c = word[i - 1];
for (int j = 0; j < 5; j++) {
if (c == "aeiou"[j]) {
if (j == 0) {
dp[i][j] = dp[i - 1][j] + 1;
} else if (dp[i - 1][j - 1] > 0) {
dp[i][j] = dp[i - 1][j] + 1;
}
}
if (j == 4) { // Complete "aeiou"
maxLength = dp[i][j] > maxLength ? dp[i][j] : maxLength;
}
}
}
return maxLength;
}
int main() {
printf("%d\n", longestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13
return 0;
}using System;
public class Solution {
public int LongestBeautifulSubstring(string word) {
int n = word.Length;
int[,] dp = new int[n + 1, 5];
int maxLength = 0;
for (int i = 1; i <= n; i++) {
char c = word[i - 1];
for (int j = 0; j < 5; j++) {
if (c == "aeiou"[j]) {
if (j == 0) {
dp[i, j] = dp[i - 1, j] + 1;
} else if (dp[i - 1, j - 1] > 0) {
dp[i, j] = dp[i - 1, j] + 1;
}
}
if (j == 4) { //Complete "aeiou"
maxLength = Math.Max(maxLength, dp[i, j]);
}
}
}
return maxLength;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LongestBeautifulSubstring("aeiaaioaaaaeiiiiouuuooaauuaeiu")); // Output: 13
}
}The Python implementation uses a list of lists as the DP table to iterate through each character in the string, updating possible valid suffix lengths for the string.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Two Pointers + Simulation
We can first transform the string word. For example, for word="aaaeiouu", we can transform it into data items ('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2) and store them in an array arr. Each data item's first element represents a vowel, and the second element represents the number of times the vowel appears consecutively. This transformation can be implemented using two pointers.
Next, we traverse the array arr, each time taking 5 adjacent data items, and judge whether the vowels in these data items are 'a', 'e', 'i', 'o', 'u' respectively. If so, calculate the total number of times the vowels appear in these 5 data items, which is the length of the current beautiful substring, and update the maximum value of the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string word.
func longestBeautifulSubstring(word string) (ans int) {
arr := []pair{}
n := len(word)
for i := 0; i < n; {
j := i
for j < n && word[j] == word[i] {
j++
}
arr = append(arr, pair{word[i], j - i})
i = j
}
for i := 0; i < len(arr)-4; i++ {
a, b, c, d, e := arr[i], arr[i+1], arr[i+2], arr[i+3], arr[i+4]
if a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u' {
ans = max(ans, a.v+b.v+c.v+d.v+e.v)
}
}
return
}
type pair struct {
c byte
v int
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) Space Complexity: O(1) |
| Dynamic Programming Approach | Time Complexity: O(n) Space Complexity: O(n) |
| Two Pointers + Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window Scan | O(n) | O(1) | Best general solution. Single pass with minimal state tracking. |
| Dynamic Programming (Vowel Stages) | O(n) | O(1) | Useful when modeling ordered transitions between character groups. |
Frequently asked questions
Is Longest Substring Of All Vowels in Order easy or hard?
The problem is rated Medium because recognizing the ordered vowel constraint and maintaining a valid substring requires careful logic. Once the sliding window idea is identified, the implementation becomes straightforward with linear time complexity.
Longest Substring Of All Vowels in Order Python/Java solution
Both Python and Java implementations follow the same logic: iterate through the string, compare each character with the previous one, and maintain the length of the current valid substring. When the substring contains all five vowels in order, update the maximum length.
How to solve Longest Substring Of All Vowels in Order in O(n)?
Traverse the string once while comparing each character with the previous one. If the vowel order stays the same or increases alphabetically, extend the current substring; otherwise reset the start. Track how many unique vowels have appeared, and when all five are present update the maximum length.
What is the best approach for Longest Substring Of All Vowels in Order?
The sliding window approach is the most efficient and commonly expected solution. It scans the string once, extending a window while vowels remain in non-decreasing alphabetical order and resetting when the order breaks. This achieves O(n) time and O(1) space.
Is Longest Substring Of All Vowels in Order asked at Google/Amazon/Meta?
This problem represents a common pattern used in interviews at large tech companies. Variations involving ordered substrings, vowel sequences, or monotonic character constraints frequently appear in interviews at companies like Amazon, Google, and Meta.
What data structure is used in Longest Substring Of All Vowels in Order?
The solution primarily uses simple variables and counters rather than complex data structures. The key technique is a sliding window over the string combined with tracking vowel transitions such as a→e→i→o→u.
What is the time complexity of Longest Substring Of All Vowels in Order?
The optimal solution runs in O(n) time where n is the length of the string. Each character is processed once during a linear scan. Space complexity is O(1) because only a few counters and the previous character need to be tracked.