# Longest Substring Of All Vowels in Order
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-substring-of-all-vowels-in-order)
Canonical: https://scaleengineer.com/dsa/problems/longest-substring-of-all-vowels-in-order
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
**Companies:** [Thomson Reuters](https://scaleengineer.com/companies/thomson-reuters)
---
## Problem
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
## Brute Force with Optimization
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Single Pass with State Tracking (Sliding Window)
This is an efficient approach that solves the problem in a single pass through the string. We use a sliding window concept, where the window represents a contiguous, non-decreasingly sorted substring of vowels. We iterate through the string, extending the window as long as the sorted order is maintained. When the order is broken, or if a new window doesn't start with 'a', we reset our counters and start a new window.
**Time:** O(N), where N is the length of `word`. We iterate through the string only once. · **Space:** O(1). We only use a few integer variables to keep track of the state, which requires constant space.
**Pros:** Highly efficient with a linear time complexity of O(N).; Optimal solution that passes for all constraints.; Uses constant extra space, making it memory efficient.
**Cons:** The logic involving state resets can be slightly more complex to reason about compared to a straightforward brute-force approach.
### Explanation
We can solve this problem optimally by iterating through the string just once. We maintain the state of the current potential beautiful substring using two variables: `currentLength` for its length and `vowelCount` for the number of unique vowels it contains.

The main idea is to identify and measure contiguous blocks of non-decreasing vowels. We iterate with a single pointer `i`:

- If we encounter a character `word.charAt(i)` that is less than the previous character `word.charAt(i-1)`, it signifies the end of the current sorted block. At this point, we must reset our counters (`currentLength` and `vowelCount`) to `0`.
- A beautiful substring must start with 'a'. So, whenever we start a new block (either at the beginning of the string or after a reset), we only proceed if the current character is 'a'.
- As we iterate and extend the current block, we increment `currentLength`. If the current character is greater than the previous one (e.g., 'e' after 'a'), it means we've encountered a new type of vowel, so we also increment `vowelCount`.
- At each step, if `vowelCount` becomes 5, it means the current substring is beautiful. We then update a global `maxLength` variable with the `currentLength`.

This method avoids re-scanning parts of the string, leading to a linear time solution.

```java
class Solution {
    public int longestBeautifulSubstring(String word) {
        int maxLength = 0;
        int currentLength = 0;
        int vowelCount = 0;

        for (int i = 0; i < word.length(); i++) {
            // Reset if the non-decreasing order is broken
            if (i > 0 && word.charAt(i) < word.charAt(i - 1)) {
                vowelCount = 0;
                currentLength = 0;
            }

            // Start a new substring if possible (must be 'a')
            if (currentLength == 0) {
                if (word.charAt(i) == 'a') {
                    currentLength = 1;
                    vowelCount = 1;
                }
            } 
            // Extend the current substring
            else {
                currentLength++;
                if (word.charAt(i) > word.charAt(i - 1)) {
                    vowelCount++;
                }
            }

            // Update max length if the current substring is beautiful
            if (vowelCount == 5) {
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`, `currentLength = 0`, and `vowelCount = 0`.
- Iterate through the string with a pointer `i` from `0` to `word.length() - 1`.
- At each character, check if the non-decreasing order is maintained compared to the previous character. If `i > 0` and `word.charAt(i) < word.charAt(i-1)`, the order is broken. Reset `currentLength = 0` and `vowelCount = 0`.
- If `currentLength` is `0`, it signifies the start of a new potential substring. A beautiful substring must start with 'a'. So, if `word.charAt(i) == 'a'`, we start a new window by setting `currentLength = 1` and `vowelCount = 1`.
- If `currentLength` is not `0`, we are extending the current valid window. Increment `currentLength`. If `word.charAt(i) > word.charAt(i-1)`, it's a new distinct vowel, so increment `vowelCount`.
- After processing the character, if `vowelCount == 5`, it means the current window represents a beautiful substring. Update `maxLength = Math.max(maxLength, currentLength)`.
- After the loop, return `maxLength`.

# Solutions
### Java

```java
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 ; } }
```

### CPP

```cpp
class Solution {
public:
  int longestBeautifulSubstring(string word) {
    vector<pair<char, int>> arr;
    int n = word.size();
    for (int i = 0; i < n;) {
      int j = i;
      while (j < n && word[j] == word[i])
        ++j;
      arr.push_back({word[i], j - i});
      i = j;
    }
    int ans = 0;
    for (int i = 0; i < (int)arr.size() - 4; ++i) {
      auto &[a, v1] = arr[i];
      auto &[b, v2] = arr[i + 1];
      auto &[c, v3] = arr[i + 2];
      auto &[d, v4] = arr[i + 3];
      auto &[e, v5] = arr[i + 4];
      if (a == 'a' && b == 'e' && c == 'i' && d == 'o' && e == 'u') {
        ans = max(ans, v1 + v2 + v3 + v4 + v5);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def longestBeautifulSubstring(self, word: str) -> int: arr = [] n = len(word) i = 0 while i < n: j = i while j < n and word[j] == word[i]: j += 1 arr . append((word[i], j - i)) i = j ans = 0 for i in range(len(arr) - 4): a, b, c, d, e = arr[i: i + 5] if a[0] + b[0] + c[0] + d[0] + e[0] == "aeiou": ans = max(ans, a[1] + b[1] + c[1] + d[1] + e[1]) return ans

```