Longest Substring Of All Vowels in Order - Practice Coding Problems

Longest Substring Of All Vowels in Order - 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.

Input & Output

Example 1 — Basic Beautiful Substring

$ Input: word = "aeiouaaaeiou"

› Output: 13

💡 Note: The longest beautiful substring is "aeiouaaaeiou" with length 13. It contains all vowels a,e,i,o,u in order.

Example 2 — Multiple Beautiful Substrings

$ Input: word = "aeiou"

› Output: 5

💡 Note: The entire string "aeiou" is beautiful with length 5. It contains each vowel exactly once in alphabetical order.

Example 3 — No Beautiful Substring

$ Input: word = "uaeio"

› Output: 0

💡 Note: No beautiful substring exists because the vowels are not in alphabetical order.

Constraints

1 ≤ word.length ≤ 5 × 10⁴
word consists of only English vowels

Visualization

Tap to expand

Understanding the Visualization

Input

String with vowels: "aeiouaaaeiou"

Process

Find substrings with all 5 vowels in alphabetical order

Output

Length of longest beautiful substring: 13

Key Takeaway

🎯 Key Insight: Track vowel sequence progress and find longest complete beautiful substring

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use a sliding window or state machine approach to track vowel sequences in alphabetical order. We start a new window when we encounter 'a' and expand it while maintaining the correct vowel order. Best approach is sliding window with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check every possible substring to see if it's beautiful
State Machine	O(n)	O(1)	Use state machine to track vowel transitions efficiently
Sliding Window	O(n)	O(1)	Track vowels and sequence order with expanding window

Brute Force — Algorithm Steps

Step 1: Try every possible starting position
Step 2: For each start, extend substring and check if beautiful
Step 3: Track maximum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try All Starts

Start from each position

Extend Length

Check each possible ending

Validate

Check if substring is beautiful

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isBeautiful(char* s, int start, int len) {
    if (len < 5) return false;
    bool vowels[5] = {false};
    char prev = 0;
    
    for (int i = 0; i < len; i++) {
        char c = s[start + i];
        if (c < prev) return false;
        prev = c;
        
        switch(c) {
            case 'a': vowels[0] = true; break;
            case 'e': vowels[1] = true; break;
            case 'i': vowels[2] = true; break;
            case 'o': vowels[3] = true; break;
            case 'u': vowels[4] = true; break;
        }
    }
    
    for (int i = 0; i < 5; i++) {
        if (!vowels[i]) return false;
    }
    return true;
}

int solution(char* word) {
    int maxLen = 0;
    int n = strlen(word);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 5; j <= n; j++) {
            if (isBeautiful(word, i, j - i)) {
                if (j - i > maxLen) {
                    maxLen = j - i;
                }
            }
        }
    }
    
    return maxLen;
}

int main() {
    char word[100001];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(word);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops for start/end positions, plus linear validation for each substring

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler