Scale Engineer

Longest Substring Of All Vowels in Order

Med
#1681Time: O(N^2), where N is the length of `word`. The nested loops lead to a quadratic time complexity. For each of the N starting positions, the inner loop can iterate up to N times.Space: O(1). The `HashSet` used to track vowels will store at most 5 distinct characters, so the space used is constant.1 company
Patterns
Sliding Window
Data structures
String
Companies
Thomson Reuters

Prompt

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'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible substring that starts at each index of the input string. For each starting position, we extend a substring one character at a time, checking if it maintains the non-decreasing vowel order. If it does, we also check if it contains all five vowels using a HashSet. We keep track of the maximum length of such a "beautiful" substring found.

Algorithm

  • Initialize maxLength = 0.
  • Loop i from 0 to word.length() - 1 to select a starting character:
    • Create a new HashSet<Character> called vowelsSeen.
    • Loop j from i to word.length() - 1 to extend the substring:
      • If j > i and word.charAt(j) < word.charAt(j-1), it means the non-decreasing order is violated. Break the inner loop as no further extension from i will be valid.
      • Add word.charAt(j) to the vowelsSeen set.
      • If vowelsSeen.size() == 5, it means the current substring word[i...j] contains all five vowels and is sorted. Update maxLength = Math.max(maxLength, j - i + 1).
  • After all loops complete, return maxLength.

Walkthrough

In this method, we iterate through the string with an outer loop, where the loop variable i represents the starting index of a potential beautiful substring. For each starting index i, we begin an inner loop with j from i to the end of the string. This inner loop extends the substring word[i...j]. Inside the inner loop, we verify two conditions for the substring word[i...j]:

  1. Sorted Order: The characters must be in non-decreasing alphabetical order. We check this by comparing word.charAt(j) with word.charAt(j-1). If word.charAt(j) < word.charAt(j-1), the order is broken. This means no further extension from i can form a validly sorted substring, so we break the inner loop.
  2. All Vowels Present: We use a HashSet to keep track of the unique vowels encountered in the current substring word[i...j].

If the substring is sorted and the HashSet contains all 5 vowels, we update our maxLength with the current substring's length (j - i + 1). After checking all possible starting positions, maxLength will hold the length of the longest beautiful substring.

import java.util.HashSet;import java.util.Set; class Solution {    public int longestBeautifulSubstring(String word) {        int n = word.length();        int maxLength = 0;         for (int i = 0; i < n; i++) {            Set<Character> vowelsSeen = new HashSet<>();            for (int j = i; j < n; j++) {                // Check for non-decreasing order                if (j > i && word.charAt(j) < word.charAt(j - 1)) {                    break; // Substring from i is no longer sorted                }                 vowelsSeen.add(word.charAt(j));                 // If all 5 vowels are present, it's a beautiful substring                if (vowelsSeen.size() == 5) {                    maxLength = Math.max(maxLength, j - i + 1);                }            }        }        return maxLength;    }}

Complexity

Time

O(N^2), where N is the length of `word`. The nested loops lead to a quadratic time complexity. For each of the N starting positions, the inner loop can iterate up to N times.

Space

O(1). The `HashSet` used to track vowels will store at most 5 distinct characters, so the space used is constant.

Trade-offs

Pros

  • Relatively simple to understand and implement.

  • Correctly solves the problem for smaller inputs.

Cons

  • Highly inefficient due to its O(N^2) time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the input sizes specified in the problem constraints.

Solutions

class Solution { public int longestBeautifulSubstring ( String word ) { int n = word . length (); List < Node > arr = new ArrayList <>(); for ( int i = 0 ; i < n ;) { int j = i ; while ( j < n && word . charAt ( j ) == word . charAt ( i )) { ++ j ; } arr . add ( new Node ( word . charAt ( i ), j - i )); i = j ; } int ans = 0 ; for ( int i = 0 ; i < arr . size () - 4 ; ++ i ) { Node a = arr . get ( i ), b = arr . get ( i + 1 ), c = arr . get ( i + 2 ), d = arr . get ( i + 3 ), e = arr . get ( i + 4 ); if ( a . c == 'a' && b . c == 'e' && c . c == 'i' && d . c == 'o' && e . c == 'u' ) { ans = Math . max ( ans , a . v + b . v + c . v + d . v + e . v ); } } return ans ; } } class Node { char c ; int v ; Node ( char c , int v ) { this . c = c ; this . v = v ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem