LeetCode 1839 - Longest Substring Of All Vowels in Order

LeetCode Problem 1839

Difficulty: 🟡 Medium
Topics: String, Sliding Window

Solution

Problem Understanding

The problem asks us to find the length of the longest substring that is considered "beautiful" according to two strict conditions.

First, the substring must contain all five vowels, 'a', 'e', 'i', 'o', and 'u', at least once.

Second, the vowels inside the substring must appear in non decreasing alphabetical order. This means every 'a' must come before every 'e', every 'e' before every 'i', and so on. Repeated vowels are allowed, but the order can never go backward.

For example:

• "aeiou" is valid because all vowels appear once and are properly ordered.
• "aaaaeiiiouuu" is also valid because vowels are grouped in sorted order.
• "aeioeu" is invalid because after 'o', the substring goes back to 'e'.
• "aaaeeeooo" is invalid because it never contains 'i' or 'u'.

The input is a string word that contains only vowels. The length of the string can be as large as 5 * 10^5, which immediately tells us that inefficient quadratic solutions will likely time out. We need an algorithm that processes the string in linear time, or very close to it.

The expected output is a single integer representing the maximum length among all beautiful substrings. If no beautiful substring exists, we return 0.

Several edge cases are important:

• A string shorter than 5 characters can never contain all five vowels.
• A string with only one repeated vowel, such as "aaaaa", is not beautiful.
• A string that repeatedly breaks alphabetical order must restart the search.
• Consecutive duplicate vowels are allowed and should extend the current substring.
• A valid substring may appear in the middle of the string rather than starting at index 0.

Approaches

Brute Force Approach

A straightforward approach is to examine every possible substring and check whether it is beautiful.

For every starting index, we can extend the ending index one character at a time. For each substring, we verify two properties:

1. The characters are in non decreasing order.
2. All five vowels appear at least once.

This works because every possible substring is checked explicitly, so the correct answer cannot be missed.

However, the performance is far too slow for the constraints. A string of length n has O(n^2) substrings. Validating each substring may take another O(n) time in the worst case, leading to O(n^3) complexity. Even with optimizations, the solution remains too slow for n = 500000.

Optimal Sliding Window / Single Pass Approach

The key observation is that a beautiful substring must consist of vowels appearing in sorted order. As we scan the string from left to right, we only need to track:

• Whether the order is still valid.
• How many distinct vowels have appeared in sequence.
• The starting position of the current valid segment.

Whenever the current character is smaller than the previous character alphabetically, the ordering rule is broken. At that point, the current substring can no longer be extended, so we must restart from the current character.

If the current character is larger than the previous character, we have transitioned to a new vowel group, so we increase the distinct vowel count.

Whenever the distinct vowel count reaches 5, we know the current substring contains all vowels in order, so we update the answer.

This allows us to process the string in a single pass.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) to O(n³)	O(1)	Checks every substring explicitly
Optimal	O(n)	O(1)	Single pass while tracking vowel transitions

Algorithm Walkthrough

1. Initialize three variables:

• start, the beginning index of the current valid segment.
• distinct_vowels, the number of vowel groups seen so far.
• max_length, the best answer found.

2. Start scanning the string from left to right, beginning at index 1 because we compare each character with the previous one.
3. If the current character is smaller than the previous character alphabetically, the vowel ordering rule has been violated.

For example:

• "aeiou" is valid.
• "aeioa" becomes invalid at 'a' because 'a' < 'o'.

When this happens:

• Reset start to the current index.
• Reset distinct_vowels to 1 because the current character starts a new sequence.

4. If the current character is larger than the previous character, we have moved to the next vowel group.

For example:

• 'a' -> 'e'
• 'e' -> 'i'

Increase distinct_vowels by 1. 5. If the current character is equal to the previous character, we remain in the same vowel group, so nothing changes. 6. Whenever distinct_vowels == 5, the current substring contains all five vowels in valid order.

Compute its length:

$$\text{length} = i - start + 1$$

Update max_length if this substring is longer. 7. Continue until the end of the string. 8. Return max_length.

Why it works

The algorithm maintains the invariant that the substring from start to the current index is always alphabetically ordered. Whenever order breaks, the substring becomes unusable and must restart.

The distinct_vowels counter tracks how many vowel transitions have occurred in order. Since the only possible vowels are 'a', 'e', 'i', 'o', and 'u', reaching 5 guarantees that all vowels have appeared in correct order.

Because every character is processed exactly once and every valid substring ending at each position is considered, the algorithm always finds the longest beautiful substring.

Python Solution

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        if len(word) < 5:
            return 0

        max_length = 0
        start = 0
        distinct_vowels = 1

        for i in range(1, len(word)):
            if word[i] < word[i - 1]:
                start = i
                distinct_vowels = 1
            elif word[i] > word[i - 1]:
                distinct_vowels += 1

            if distinct_vowels == 5:
                max_length = max(max_length, i - start + 1)

        return max_length

The implementation begins with a quick optimization. If the string length is smaller than 5, it is impossible to contain all five vowels, so we immediately return 0.

The variable start stores the beginning index of the current ordered substring. The variable distinct_vowels tracks how many different vowel groups have appeared so far.

Inside the loop, we compare the current character with the previous one.

If the current character is smaller, the ordering rule has been broken. We reset the current segment and begin a new one from the current position.

If the current character is larger, we have encountered a new vowel group, so we increment distinct_vowels.

If the current character equals the previous one, we stay within the same vowel group and continue extending the substring.

Whenever distinct_vowels becomes 5, we know the substring contains all vowels in order, so we update the answer using the current window length.

The solution uses constant extra memory and processes the string in linear time.

Go Solution

func longestBeautifulSubstring(word string) int {
    if len(word) < 5 {
        return 0
    }

    maxLength := 0
    start := 0
    distinctVowels := 1

    for i := 1; i < len(word); i++ {
        if word[i] < word[i-1] {
            start = i
            distinctVowels = 1
        } else if word[i] > word[i-1] {
            distinctVowels++
        }

        if distinctVowels == 5 {
            currentLength := i - start + 1
            if currentLength > maxLength {
                maxLength = currentLength
            }
        }
    }

    return maxLength
}

The Go implementation follows the exact same logic as the Python version. Since strings in Go are byte indexed and the input contains only lowercase English vowels, direct indexing with word[i] is completely safe.

No special handling for integer overflow is necessary because the maximum string length is only 500000, well within Go's int range.

Worked Examples

Example 1

Input:

word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"

We trace the important transitions.

Index	Character	Action	Distinct Vowels	Start	Current Length	Max
0	a	Start sequence	1	0	1	0
1	e	New vowel group	2	0	2	0
2	i	New vowel group	3	0	3	0
3	a	Order broken, reset	1	3	1	0
4	a	Same vowel	1	3	2	0
5	i	New vowel group	2	3	3	0
6	o	New vowel group	3	3	4	0
7	a	Order broken, reset	1	7	1	0
...	...	...	...	...	...	...
19	u	All vowels reached	5	7	13	13

The longest valid substring becomes:

"aaaaeiiiiouuu"

Length:

13

Example 2

Input:

word = "aeeeiiiioooauuuaeiou"

Index	Character	Action	Distinct Vowels	Start	Max
0	a	Start	1	0	0
1	e	New vowel	2	0	0
5	i	New vowel	3	0	0
9	o	New vowel	4	0	0
12	a	Order broken	1	12	0
16	a	Start new valid chain	1	16	0
17	e	New vowel	2	16	0
18	i	New vowel	3	16	0
19	o	New vowel	4	16	0
20	u	New vowel	5	16	5

The longest beautiful substring is:

"aeiou"

Length:

5

Example 3

Input:

word = "a"

The string length is less than 5, so it is impossible to contain all vowels.

Output:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single left to right scan of the input string. Every iteration performs constant time comparisons and updates, so the total running time is linear in the size of the input.

The memory usage remains constant because the algorithm stores only a few integer variables regardless of input size.

Test Cases

solution = Solution()

assert solution.longestBeautifulSubstring(
    "aeiaaioaaaaeiiiiouuuooaauuaeiu"
) == 13  # Provided example with long valid segment

assert solution.longestBeautifulSubstring(
    "aeeeiiiioooauuuaeiou"
) == 5  # Provided example where only small segment works

assert solution.longestBeautifulSubstring(
    "a"
) == 0  # Single character cannot contain all vowels

assert solution.longestBeautifulSubstring(
    "aeiou"
) == 5  # Smallest possible beautiful substring

assert solution.longestBeautifulSubstring(
    "aaaaaeiiiiiooooouuuuu"
) == 21  # Long valid substring with repetitions

assert solution.longestBeautifulSubstring(
    "aaaaa"
) == 0  # Only one vowel present

assert solution.longestBeautifulSubstring(
    "aeio"
) == 0  # Missing 'u'

assert solution.longestBeautifulSubstring(
    "uaeiou"
) == 5  # Reset required after leading 'u'

assert solution.longestBeautifulSubstring(
    "aeeiouu"
) == 7  # Valid ordered substring

assert solution.longestBeautifulSubstring(
    "aeiaeiou"
) == 5  # Multiple resets before valid substring

assert solution.longestBeautifulSubstring(
    "aaaaeeeeiiiioooouuuu"
) == 21  # Entire string is beautiful

assert solution.longestBeautifulSubstring(
    "eiiiouu"
) == 0  # Missing starting 'a'

assert solution.longestBeautifulSubstring(
    "aeiouuuaeiou"
) == 8  # Multiple valid substrings

Test	Why
"aeiaaioaaaaeiiiiouuuooaauuaeiu"	Verifies long internal valid substring
"aeeeiiiioooauuuaeiou"	Verifies reset behavior
"a"	Smallest boundary case
"aeiou"	Minimum valid beautiful substring
"aaaaaeiiiiiooooouuuuu"	Large grouped repetitions
"aaaaa"	Missing vowels
"aeio"	Missing final vowel
"uaeiou"	Leading invalid character
"aeeiouu"	Simple valid case
"aeiaeiou"	Multiple ordering resets
"aaaaeeeeiiiioooouuuu"	Entire string valid
"eiiiouu"	Missing initial vowel
"aeiouuuaeiou"	Multiple beautiful substrings

Edge Cases

One important edge case occurs when the input string is shorter than five characters. Since a beautiful substring must contain all five vowels at least once, any string shorter than five can never satisfy the requirement. The implementation handles this immediately with an early return of 0.

Another tricky case happens when alphabetical order breaks in the middle of a candidate substring. For example, in "aeioa", the final 'a' violates the ordering rule because it appears after 'o'. A naive implementation might accidentally continue counting from the old substring. The algorithm correctly resets both the starting index and the distinct vowel count whenever it detects a decreasing transition.

A third important edge case involves repeated vowels. Consecutive duplicate vowels are completely valid and should extend the substring rather than restarting it. For example, "aaaaeeeeiiiioooouuuu" is entirely beautiful. The implementation handles this by doing nothing when adjacent characters are equal, allowing the current substring to continue growing naturally.

A final subtle case occurs when the string begins with a vowel other than 'a'. For example, "eiiiouu" contains ordered vowels but is still invalid because a beautiful substring must include all five vowels beginning with 'a'. The algorithm naturally handles this because the distinct vowel count never reaches 5, so the answer remains 0.