1839. Longest Substring Of All Vowels in Order - Leetcode Solution

Code Implementation

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        vowels = 'aeiou'
        max_len, curr_len, count = 0, 0, 0
        prev = ''
        for i, c in enumerate(word):
            if c not in vowels:
                curr_len = 0
                count = 0
                prev = ''
            else:
                if curr_len == 0 or c < prev:
                    curr_len = 1
                    count = 1 if c == 'a' else 0
                else:
                    if c == prev:
                        curr_len += 1
                    elif vowels.find(c) == vowels.find(prev) + 1:
                        curr_len += 1
                        count += 1
                    else:
                        curr_len = 1 if c == 'a' else 0
                        count = 1 if c == 'a' else 0
                prev = c
                if count == 5:
                    max_len = max(max_len, curr_len)
        return max_len

class Solution {
public:
    int longestBeautifulSubstring(string word) {
        string vowels = "aeiou";
        int max_len = 0, curr_len = 0, count = 0;
        char prev = 0;
        for (int i = 0; i < word.length(); ++i) {
            char c = word[i];
            if (vowels.find(c) == string::npos) {
                curr_len = 0;
                count = 0;
                prev = 0;
            } else {
                if (curr_len == 0 || c < prev) {
                    curr_len = 1;
                    count = (c == 'a') ? 1 : 0;
                } else {
                    if (c == prev) {
                        curr_len++;
                    } else if (vowels.find(c) == vowels.find(prev) + 1) {
                        curr_len++;
                        count++;
                    } else {
                        curr_len = (c == 'a') ? 1 : 0;
                        count = (c == 'a') ? 1 : 0;
                    }
                }
                prev = c;
                if (count == 5) {
                    max_len = max(max_len, curr_len);
                }
            }
        }
        return max_len;
    }
};

class Solution {
    public int longestBeautifulSubstring(String word) {
        String vowels = "aeiou";
        int maxLen = 0, currLen = 0, count = 0;
        char prev = 0;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (vowels.indexOf(c) == -1) {
                currLen = 0;
                count = 0;
                prev = 0;
            } else {
                if (currLen == 0 || c < prev) {
                    currLen = 1;
                    count = (c == 'a') ? 1 : 0;
                } else {
                    if (c == prev) {
                        currLen++;
                    } else if (vowels.indexOf(c) == vowels.indexOf(prev) + 1) {
                        currLen++;
                        count++;
                    } else {
                        currLen = (c == 'a') ? 1 : 0;
                        count = (c == 'a') ? 1 : 0;
                    }
                }
                prev = c;
                if (count == 5) {
                    maxLen = Math.max(maxLen, currLen);
                }
            }
        }
        return maxLen;
    }
}

var longestBeautifulSubstring = function(word) {
    const vowels = "aeiou";
    let maxLen = 0, currLen = 0, count = 0;
    let prev = "";
    for (let i = 0; i < word.length; i++) {
        let c = word[i];
        if (!vowels.includes(c)) {
            currLen = 0;
            count = 0;
            prev = "";
        } else {
            if (currLen === 0 || c < prev) {
                currLen = 1;
                count = (c === 'a') ? 1 : 0;
            } else {
                if (c === prev) {
                    currLen++;
                } else if (vowels.indexOf(c) === vowels.indexOf(prev) + 1) {
                    currLen++;
                    count++;
                } else {
                    currLen = (c === 'a') ? 1 : 0;
                    count = (c === 'a') ? 1 : 0;
                }
            }
            prev = c;
            if (count === 5) {
                maxLen = Math.max(maxLen, currLen);
            }
        }
    }
    return maxLen;
};

Problem Description

Given a string word consisting only of lowercase English letters, find the length of the longest substring that contains all five English vowels ('a', 'e', 'i', 'o', 'u') in order and consecutively (they may appear multiple times, but the order must be strictly a → e → i → o → u). The substring must not skip any vowels or have them out of order, but each vowel can appear multiple times in a row. Return the length of the longest such substring. If no such substring exists, return 0.

Thought Process

At first glance, the problem seems to suggest checking every possible substring to see if it contains all five vowels in order, which would be very inefficient. However, by carefully examining the conditions, we notice:

We only care about substrings where vowels appear in the correct order, possibly with repeats.
We can process the string left-to-right, tracking the current sequence of vowels and their order.
If a character breaks the order or is not a vowel, we reset our tracking.

This leads us to think about a single-pass solution using counters to track the order and length of the current valid substring. This is much more efficient than checking all substrings.

Solution Approach

To solve the problem efficiently, we use a linear scan with state tracking:

Initialize variables to keep track of the current substring length, the number of unique vowels seen in order, and the previous character.
Iterate through each character in word:

If the character is not a vowel, reset all tracking variables.
If starting a new substring (current length is 0) or the order is broken (current char is less than previous), reset and start from this character if it's 'a'.
If the character is the same as the previous, increment the current length.
If the character is the next vowel in order, increment both the current length and the vowel count.
If the order is wrong (jumping to a non-consecutive vowel), reset and start over if it's 'a'.

If we've seen all five vowels in order, update the maximum length found.
Continue until the end of the string and return the maximum length found.

This approach ensures we only process each character once, and always know if our current substring is valid.

Example Walkthrough

Let's walk through the input word = "aeiaaioaaaaeiiiiouuuooaauuaeiu":

Start at index 0, character 'a': start a new substring, vowel count = 1, length = 1.
Next, 'e': correct order, vowel count = 2, length = 2.
Next, 'i': correct order, vowel count = 3, length = 3.
Next, 'a': order broken (goes back to 'a'), reset, start new substring.
Continue, looking for a sequence where vowels go a → e → i → o → u with no breaks.
At substring "aaaaeiiiiouuu" (indices 6 to 18), we see all vowels in order, with length 13.
Keep iterating, update max length if a longer valid substring is found.
Final answer for this input: 13.

Time and Space Complexity

Brute-force approach: Checking all substrings for validity would require O(N²) time, where N is the length of the string, and O(1) space.
Optimized approach (used here): We scan the string once, updating counters in O(1) time per character, for a total of O(N) time and O(1) space.

The improvement comes from not generating substrings, but simply tracking the needed information as we scan.

Summary

This problem is elegantly solved by recognizing that we can process the string in a single pass, using counters to ensure the vowels are in order and contiguous. By resetting whenever the order is broken, and updating the maximum length when all vowels are present, we achieve an efficient and readable solution. The key insight is to track the order and presence of vowels dynamically, rather than examining all possible substrings.

AlgoMap.io

Want Help Cracking FAANG?