Move from brute-force thinking to an efficient approach using sliding window strategy.
A string is considered beautiful if it satisfies the following conditions:
'a', 'e', 'i', 'o', 'u') must appear at least once in it.'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 * 105word consists of characters 'a', 'e', 'i', 'o', and 'u'.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Sliding Window
"aeiaaioaaaaeiiiiouuuooaauuaeiu"
"aeeeiiiioooauuuaeiou"
"a"
count-vowel-substrings-of-a-string)longest-nice-subarray)count-of-substrings-containing-every-vowel-and-k-consonants-ii)count-of-substrings-containing-every-vowel-and-k-consonants-i)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1839: Longest Substring Of All Vowels in Order
class Solution {
public int longestBeautifulSubstring(String word) {
int n = word.length();
List<Node> arr = new ArrayList<>();
for (int i = 0; i < n;) {
int j = i;
while (j < n && word.charAt(j) == word.charAt(i)) {
++j;
}
arr.add(new Node(word.charAt(i), j - i));
i = j;
}
int ans = 0;
for (int i = 0; i < arr.size() - 4; ++i) {
Node a = arr.get(i), b = arr.get(i + 1), c = arr.get(i + 2), d = arr.get(i + 3),
e = arr.get(i + 4);
if (a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u') {
ans = Math.max(ans, a.v + b.v + c.v + d.v + e.v);
}
}
return ans;
}
}
class Node {
char c;
int v;
Node(char c, int v) {
this.c = c;
this.v = v;
}
}
// Accepted solution for LeetCode #1839: Longest Substring Of All Vowels in Order
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
}
# Accepted solution for LeetCode #1839: Longest Substring Of All Vowels in Order
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
arr = []
n = len(word)
i = 0
while i < n:
j = i
while j < n and word[j] == word[i]:
j += 1
arr.append((word[i], j - i))
i = j
ans = 0
for i in range(len(arr) - 4):
a, b, c, d, e = arr[i : i + 5]
if a[0] + b[0] + c[0] + d[0] + e[0] == "aeiou":
ans = max(ans, a[1] + b[1] + c[1] + d[1] + e[1])
return ans
// Accepted solution for LeetCode #1839: Longest Substring Of All Vowels in Order
struct Solution;
impl Solution {
fn longest_beautiful_substring(word: String) -> i32 {
let word: Vec<char> = word.chars().collect();
let vowels: Vec<char> = vec!['a', 'e', 'i', 'o', 'u'];
let mut start = 0;
let n = word.len();
let mut res = 0;
'outer: while start < n {
while start < n && word[start] != 'a' {
start += 1;
}
let mut end = start;
for i in 0..5 {
if !(end < n && word[end] == vowels[i]) {
start = end;
continue 'outer;
}
while end < n && word[end] == vowels[i] {
end += 1;
}
}
res = res.max(end - start);
start = end;
}
res as i32
}
}
#[test]
fn test() {
let word = "aeiaaioaaaaeiiiiouuuooaauuaeiu".to_string();
let res = 13;
assert_eq!(Solution::longest_beautiful_substring(word), res);
let word = "aeeeiiiioooauuuaeiou".to_string();
let res = 5;
assert_eq!(Solution::longest_beautiful_substring(word), res);
let word = "a".to_string();
let res = 0;
assert_eq!(Solution::longest_beautiful_substring(word), res);
}
// Accepted solution for LeetCode #1839: Longest Substring Of All Vowels in Order
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1839: Longest Substring Of All Vowels in Order
// class Solution {
// public int longestBeautifulSubstring(String word) {
// int n = word.length();
// List<Node> arr = new ArrayList<>();
// for (int i = 0; i < n;) {
// int j = i;
// while (j < n && word.charAt(j) == word.charAt(i)) {
// ++j;
// }
// arr.add(new Node(word.charAt(i), j - i));
// i = j;
// }
// int ans = 0;
// for (int i = 0; i < arr.size() - 4; ++i) {
// Node a = arr.get(i), b = arr.get(i + 1), c = arr.get(i + 2), d = arr.get(i + 3),
// e = arr.get(i + 4);
// if (a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u') {
// ans = Math.max(ans, a.v + b.v + c.v + d.v + e.v);
// }
// }
// return ans;
// }
// }
//
// class Node {
// char c;
// int v;
//
// Node(char c, int v) {
// this.c = c;
// this.v = v;
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each starting index, scan the next k elements to compute the window aggregate. There are n−k+1 starting positions, each requiring O(k) work, giving O(n × k) total. No extra space since we recompute from scratch each time.
The window expands and contracts as we scan left to right. Each element enters the window at most once and leaves at most once, giving 2n total operations = O(n). Space depends on what we track inside the window (a hash map of at most k distinct elements, or O(1) for a fixed-size window).
Review these before coding to avoid predictable interview regressions.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.