{x}
blog image

Longest Substring Of All Vowels in Order

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

Solution Explanation: Longest Beautiful Substring

This problem asks to find the length of the longest substring within a given string that contains all five vowels ('a', 'e', 'i', 'o', 'u') in order. The solution uses a two-pointer approach with a slight optimization to group consecutive vowels.

Algorithm:

  1. Consecutive Vowel Grouping: The input string word is processed to group consecutive identical vowels. This is done efficiently using a sliding window technique. The result is stored in a list (or array) of pairs, where each pair (char, count) represents a vowel and the number of consecutive times it appears.

  2. Sliding Window Check: A sliding window of size 5 is used to iterate through the grouped vowels. For each window, the algorithm checks:

    • If the window contains 'a', 'e', 'i', 'o', 'u' in that order.
    • If it does, it calculates the total length of the substring represented by the window by summing the counts of each vowel.
    • The maximum length found so far is updated.

  3. Return the Maximum Length: After iterating through all possible windows, the function returns the maximum length of a beautiful substring found. If no beautiful substring is found, it returns 0.

Time Complexity: O(n), where n is the length of the input string. The string is traversed once to group the vowels, and then again to check the 5-vowel windows. The sliding window check takes linear time in the worst case.

Space Complexity: O(n) in the worst case. This is because, in the worst case scenario where all characters are different, the array of grouped vowels can have size proportional to n. However, if there are many consecutive vowels, the space used will be much less than n.

Code Examples:

The provided code examples in Python, Java, C++, and Go all implement the same algorithm. They differ slightly in syntax and data structure usage, but the core logic remains the same. Here's a breakdown of the common elements:

  • arr (or equivalent): This variable stores the grouped vowels (pairs of vowel and its consecutive count).
  • Looping and windowing: The outer loop iterates through the arr, creating a 5-element window for each iteration. The inner conditions check the order and type of vowels.
  • ans: This variable keeps track of the maximum length found so far.
  • max() (or equivalent): This function updates ans to the maximum between the current ans and the length of a newly discovered beautiful substring.

The Java code uses a custom Node class for better readability and organization of vowel data. Other languages use tuples or similar structures.

Example Walkthrough (Python):

Let's consider the input word = "aeiaaioaaaaeiiiiouuuooaauuaeiu".

  1. Grouping: The algorithm will produce a list similar to [('a', 2), ('e', 1), ('i', 2), ('a', 1), ('o', 2), ('a', 4), ('e', 4), ('i', 4), ('o', 3), ('u', 3), ('o', 2), ('a', 2), ('u', 1), ('a', 1), ('e', 1), ('i', 1), ('u', 1)].

  2. Sliding Window: The sliding window will iterate, identifying the window [('a', 4), ('e', 4), ('i', 4), ('o', 3), ('u', 3)]. This window contains all five vowels in order, and its total length (4 + 4 + 4 + 3 + 3 = 18) is not the correct answer, however this is an example of a longer than expected calculation.

  3. Maximum Length: The algorithm continues to iterate through all possible 5-vowel windows and keeps track of the maximum length, eventually correctly determining the longest beautiful substring as "aaaaeiiiiouuu" with length 13.