Longest Substring Of All Vowels in Order

Medium

Asked by:

11 views

Topics:

StringsTwo Pointers

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 * 10⁵
word consists of characters 'a', 'e', 'i', 'o', and 'u'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible length of the input string `word`?
What should be returned if the input string `word` is empty or null?
If no valid substring exists (i.e., there are no vowels in the correct order), what should be returned?
Can the input string `word` contain characters other than lowercase English letters?
Does a substring need to contain all vowels ('a', 'e', 'i', 'o', 'u') to be considered valid, or can it contain only a subset of the vowels in the correct order?

Brute Force Solution

Approach

The brute force method for finding the longest vowel substring means checking every possible substring within the given text. We'll consider each possible starting point and ending point for a substring. For each substring, we then verify if it only contains vowels in the required order and if it is longer than the best substring we've found so far.

Here's how the algorithm would work step-by-step:

Start by picking a starting position in the text.
From that starting position, consider every possible ending position to create a substring.
Check if the substring contains only the vowels 'a', 'e', 'i', 'o', 'u' in that exact order.
If the substring has vowels in the wrong order, ignore it.
If the substring has vowels in the correct order, and it's longer than any other vowel substring we've seen so far, remember it.
Repeat this process by moving the starting position to the next spot in the original text and trying every ending position from there.
Once you've checked every possible starting and ending position, the longest vowel-only substring you remembered is the answer.

Code Implementation

def longest_substring_of_all_vowels_in_order_brute_force(input_string):
    longest_substring_length = 0

    for i in range(len(input_string)): 
        for j in range(i, len(input_string)):
            substring = input_string[i:j+1]

            is_all_vowels = True
            for char in substring:
                if char not in 'aeiou':
                    is_all_vowels = False
                    break

            if is_all_vowels:
                # Check if the vowels are in order
                is_in_order = True
                expected_vowel_index = 0
                vowels = 'aeiou'
                for char in substring:
                    if char == vowels[expected_vowel_index]:
                        if expected_vowel_index < 4:
                            expected_vowel_index += 1
                    elif char in vowels[expected_vowel_index:]:
                        is_in_order = False
                        break
                    else:
                        is_in_order = False
                        break

                # Update the longest substring length if the substring meets the conditions.
                if is_in_order:
                    substring_length = len(substring)
                    longest_substring_length = max(longest_substring_length, substring_length)

    return longest_substring_length

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible substrings of the input string of length n. The outer loop iterates n times, selecting a starting position. The inner loop iterates up to n times from the starting position to the end, defining the substring's end. Inside the inner loop, we validate if the created substring contains only vowels in the correct order. This validation, in the worst-case scenario, requires examining each character of the substring, taking up to n operations. Thus, we have nested loops (n * n) with validation inside (n) making the total operations approximate n * n * n, resulting in O(n³).

Space Complexity

O(1) – The brute force approach iterates through substrings of the input string. It only uses a few constant space variables to keep track of the start and end indices of the current substring, and to store the longest vowel substring found so far. The space required by these variables does not depend on the length of the input string, denoted as N. Thus, the space complexity is constant.

Optimal Solution

Approach

To find the longest valid substring, we'll use a focused approach that efficiently scans the input. We carefully track our progress through the vowels and reset when we encounter an invalid sequence, avoiding unnecessary checks. This method only examines each character a few times, which makes it super fast.

Here's how the algorithm would work step-by-step:

Start scanning the input text from left to right, one character at a time.
Check if the current character is the vowel we expect in the sequence (a, then e, then i, then o, then u).
If it is the expected vowel, advance to the next expected vowel and extend the potential substring.
If it is NOT the expected vowel, there are two cases: either we got the correct vowel out of order (e.g. an 'e' when 'a' was expected, meaning the vowel order is broken), or we got a character that isn't a vowel at all.
If the vowel order is broken or we find a non-vowel, reset the potential substring to start fresh at the next character. However, if the current character IS the 'a' we are looking for, we can start a NEW potential substring right away!
Keep track of the longest valid substring found so far.
After scanning the entire input text, the longest substring you have tracked is the answer.

Code Implementation

def longest_substring_of_all_vowels_in_order(word):
    vowels = 'aeiou'
    vowel_index = 0
    max_length = 0
    current_length = 0

    for char in word:
        if char == vowels[vowel_index]:
            current_length += 1
            vowel_index += 1

            # If we've reached the last vowel, reset the index.
            if vowel_index == len(vowels):
                max_length = max(max_length, current_length)
                vowel_index = 0

        else:
            # Start building a new string if current char is 'a'.
            if char == 'a':
                vowel_index = 1
                current_length = 1

            # Otherwise, reset and search from this point onwards.
            else:
                max_length = max(max_length, current_length)
                current_length = 0
                vowel_index = 0

    max_length = max(max_length, current_length)

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once. During this single pass, it checks each character against the expected vowel sequence. While there are resets to the potential substring, each character is still visited and examined a constant number of times. Therefore, the time complexity is directly proportional to the input size n, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a constant number of variables to keep track of the current vowel being searched for and the length of the longest valid substring. There are no auxiliary data structures whose size depends on the length of the input string. Therefore, the space complexity is independent of the input size N, and remains constant.

Edge Cases

Case	How to Handle
Empty input string	Return 0 as there are no vowels in order.
Input string with no vowels	Return 0 as there is no valid substring.
Input string with only one vowel	Return 1 if the single character is a vowel, 0 otherwise.
Input string with vowels in reverse order or mixed order	The algorithm should correctly identify substrings that violate the vowel order and not include them in the longest substring calculation.
Input string containing only 'a's	Return the length of the string.
Input string like 'aeiou'	Return the length of the string since it's a valid substring.
Long input string to ensure efficiency (e.g., length = 10^5)	The algorithm should have a time complexity that allows it to process long strings without timing out, ideally O(n).
Input with repeated valid substrings interspersed with invalid characters, e.g. 'aaeei oou'	The algorithm should reset the valid substring count when an invalid vowel or non-vowel is encountered.

Empty input string

How to Handle:

Return 0 as there are no vowels in order.

Input string with no vowels

How to Handle:

Return 0 as there is no valid substring.

Input string with only one vowel

How to Handle:

Return 1 if the single character is a vowel, 0 otherwise.

Input string with vowels in reverse order or mixed order

How to Handle:

The algorithm should correctly identify substrings that violate the vowel order and not include them in the longest substring calculation.

Input string containing only 'a's

How to Handle:

Return the length of the string.

Input string like 'aeiou'

How to Handle:

Return the length of the string since it's a valid substring.

Long input string to ensure efficiency (e.g., length = 10^5)

How to Handle:

The algorithm should have a time complexity that allows it to process long strings without timing out, ideally O(n).

Input with repeated valid substrings interspersed with invalid characters, e.g. 'aaeei oou'

How to Handle:

The algorithm should reset the valid substring count when an invalid vowel or non-vowel is encountered.