Skip to main content

Longest Substring Of All Vowels in Order

Problem Description​

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.

Examples​

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.

Constraints​

  • 1 <= s.length <= 10^5

Solution for Longest Substring Of All Vowels in Order Problem​

Approach​

  1. Initialization:

    • Use a map mp to assign numeric values to each vowel based on their alphabetical order: 'a' = 1, 'e' = 2, 'i' = 3, 'o' = 4, 'u' = 5.
    • Initialize variables i to iterate through the string and len to store the maximum length of the valid substring found.

  2. Iterate Through the String:

    • Start iterating from the beginning of the string word.
    • Whenever encountering the first character 'a', begin checking for the sequence of vowels 'a', 'e', 'i', 'o', 'u'.
    • Use a set st to track which vowels have been seen in the current sequence.

  3. Check for Valid Substring:

    • If the current character is 'a', add it to the set st.
    • Continue iterating through the string while the next character maintains the order defined by mp (i.e., mp[word[i]] <= mp[word[i + 1]]) and add each vowel encountered to st.
    • If st contains all five vowels after processing a valid substring, update len with the maximum length found.

  4. Return the Result:

    • After iterating through the entire string, len will hold the length of the longest valid substring found. If no such substring exists where all five vowels are present in order, return 0.

Implementation​

Live Editor
function Solution(arr) {
 function   longestBeautifulSubstring(word) {
    const mp = { 'a': 1, 'e': 2, 'i': 3, 'o': 4, 'u': 5 };
    let i = 0;
    let len = 0;

    while (i < word.length) {
        const start = i;
        const st = new Set();
        if (word[i] === 'a') {
            st.add(word[i]);
            while (i < word.length - 1 && mp[word[i]] <= mp[word[i + 1]]) {
                i++;
                st.add(word[i]);
            }
            if (st.size === 5) {
                len = Math.max(len, i - start + 1);
            }
        }
        i++;
    }
    return len;
}
  const input = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
  const output = longestBeautifulSubstring(input) ;
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(nlogn)O(nlogn) because of sorting, where n is the size of array
  • Space Complexity: O(n)O(n)

Code in Different Languages​

Written by @hiteshgahanolia
class Solution {
 longestBeautifulSubstring(word) {
     const mp = { 'a': 1, 'e': 2, 'i': 3, 'o': 4, 'u': 5 };
     let i = 0;
     let len = 0;

     while (i < word.length) {
         const start = i;
         const st = new Set();
         if (word[i] === 'a') {
             st.add(word[i]);
             while (i < word.length - 1 && mp[word[i]] <= mp[word[i + 1]]) {
                 i++;
                 st.add(word[i]);
             }
             if (st.size === 5) {
                 len = Math.max(len, i - start + 1);
             }
         }
         i++;
     }
     return len;
 }
}

References​