Problem Description

You need to find the longest "beautiful" substring in a string that contains only vowels ('a', 'e', 'i', 'o', 'u').

A substring is considered beautiful if it meets two conditions:

1. It contains all 5 vowels at least once
2. The vowels appear in alphabetical order (all 'a's come before 'e's, all 'e's come before 'i's, and so on)

For example:

• "aeiou" is beautiful - has all vowels in order
• "aaaaaaeiiiioou" is beautiful - has all vowels in order with repetitions allowed
• "uaeio" is NOT beautiful - vowels are not in alphabetical order
• "aeoiu" is NOT beautiful - 'o' comes before 'i', breaking alphabetical order
• "aaaeeeooo" is NOT beautiful - missing vowels 'i' and 'u'

Given a string word consisting only of English vowels, return the length of the longest beautiful substring. If no beautiful substring exists, return 0.

The solution approach groups consecutive identical vowels together into (vowel, count) pairs. For instance, "aaaeiouu" becomes [('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2)]. Then it checks every sequence of 5 consecutive groups to see if they form the pattern "aeiou" in order. If they do, the sum of their counts gives the length of that beautiful substring. The algorithm tracks the maximum length found.

Intuition

The key insight is that a beautiful substring must have exactly 5 distinct segments of vowels appearing in the specific order 'a', 'e', 'i', 'o', 'u'. Each segment can have one or more of the same vowel repeated consecutively.

Think about what a beautiful substring looks like: it could be "aeiou" (minimal case) or "aaaeeeiiioooouuuu" (with repetitions). Notice that we always have groups of consecutive identical vowels, and these groups must follow the alphabetical pattern.

This observation leads us to transform the problem. Instead of checking every possible substring character by character, we can group consecutive identical vowels together. For example, "aaaeiouu" becomes a sequence of groups: [('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2)].

Once we have this grouped representation, finding a beautiful substring becomes much simpler - we just need to find sequences of exactly 5 consecutive groups where the vowels are 'a', 'e', 'i', 'o', 'u' in that order. The length of such a beautiful substring is simply the sum of counts in these 5 groups.

Why does this work? Because any beautiful substring must transition from 'a' to 'e' to 'i' to 'o' to 'u' exactly once (no going back), and within each vowel section, we can have any number of repetitions. By grouping consecutive vowels, we capture this structure perfectly and can check the pattern efficiently by looking at sequences of 5 groups at a time.

Learn more about Sliding Window patterns.

Solution Approach

The implementation follows a two-phase approach: transformation and validation.

Phase 1: Transform the string into groups

We use two pointers to group consecutive identical vowels. Starting with pointer i at position 0:

• Set pointer j = i
• Move j forward while word[j] == word[i] (same vowel)
• Create a tuple (word[i], j - i) where the first element is the vowel and the second is its count
• Move i to j and repeat until we've processed the entire string

For example, "aaaeiouu" transforms into arr = [('a', 3), ('e', 1), ('i', 1), ('o', 1), ('u', 2)].

Phase 2: Find beautiful substrings

We iterate through the array arr and examine every sequence of 5 consecutive groups:

• For position i, extract 5 groups: a, b, c, d, e = arr[i : i + 5]
• Check if the vowels form the pattern "aeiou" by concatenating the first elements: a[0] + b[0] + c[0] + d[0] + e[0] == "aeiou"
• If the pattern matches, calculate the total length: a[1] + b[1] + c[1] + d[1] + e[1]
• Track the maximum length found

The loop runs from i = 0 to len(arr) - 4 to ensure we always have 5 groups to examine.

Why this works:

• Any beautiful substring must contain exactly 5 distinct vowel segments in alphabetical order
• By grouping consecutive vowels, we reduce the problem to pattern matching on groups
• A sliding window of size 5 on the groups array captures all possible beautiful substrings
• The time complexity is O(n) for transformation plus O(m) for validation where m is the number of groups (m ≤ n)

Example Walkthrough

Let's walk through the solution with the string word = "aaeiiouuuaaaeeiou".

Step 1: Transform into groups

We scan through the string and group consecutive identical vowels:

• Start at index 0: 'a' appears twice → ('a', 2)
• Move to index 2: 'e' appears once → ('e', 1)
• Move to index 3: 'i' appears twice → ('i', 2)
• Move to index 5: 'o' appears once → ('o', 1)
• Move to index 6: 'u' appears three times → ('u', 3)
• Move to index 9: 'a' appears three times → ('a', 3)
• Move to index 12: 'e' appears twice → ('e', 2)
• Move to index 14: 'i' appears once → ('i', 1)
• Move to index 15: 'o' appears once → ('o', 1)
• Move to index 16: 'u' appears once → ('u', 1)

Result: arr = [('a', 2), ('e', 1), ('i', 2), ('o', 1), ('u', 3), ('a', 3), ('e', 2), ('i', 1), ('o', 1), ('u', 1)]

Step 2: Check sequences of 5 groups

Now we slide a window of size 5 across the array:

• Window at index 0-4: [('a', 2), ('e', 1), ('i', 2), ('o', 1), ('u', 3)]

  • Vowels: 'a' + 'e' + 'i' + 'o' + 'u' = "aeiou" ✓
  • This is beautiful! Length = 2 + 1 + 2 + 1 + 3 = 9
  • Update max_length = 9

• Window at index 1-5: [('e', 1), ('i', 2), ('o', 1), ('u', 3), ('a', 3)]

  • Vowels: 'e' + 'i' + 'o' + 'u' + 'a' = "eioua" ✗
  • Not the pattern "aeiou", skip

• Window at index 2-6: [('i', 2), ('o', 1), ('u', 3), ('a', 3), ('e', 2)]

  • Vowels: 'i' + 'o' + 'u' + 'a' + 'e' = "iouae" ✗
  • Not the pattern "aeiou", skip

• Continue sliding...

• Window at index 5-9: [('a', 3), ('e', 2), ('i', 1), ('o', 1), ('u', 1)]

  • Vowels: 'a' + 'e' + 'i' + 'o' + 'u' = "aeiou" ✓
  • This is beautiful! Length = 3 + 2 + 1 + 1 + 1 = 8
  • max_length remains 9 (since 9 > 8)

Result: The longest beautiful substring has length 9, corresponding to the substring "aaeiiouu" from the original string.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string word.

The algorithm makes a single pass through the string to build the arr list. In the first while loop, each character is visited exactly once as the pointer i moves from 0 to n. Even though there's a nested while loop with pointer j, it doesn't increase the complexity because j starts where i is and moves forward, and then i jumps to where j ended. This ensures each character is processed only once.

The second loop iterates through the arr list, which in the worst case has at most n elements (when every character is different). The loop performs constant time operations for each window of size 5, making this part also O(n).

The space complexity is O(n). The arr list stores tuples containing characters and their counts. In the worst case, when all characters are different, the arr list will have n tuples. Each tuple takes constant space, so the total space used is proportional to the number of groups, which is at most n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Assuming Any 5 Groups Form a Valid Substring

The Problem: A common mistake is assuming that any 5 consecutive groups in the array automatically represent a contiguous substring in the original string. However, the grouping process only ensures that identical consecutive characters are grouped together - it doesn't validate that these groups form a continuous sequence containing all required vowels in order.

Why This Happens: Developers might overlook that the string could have patterns like "aeiouaeiou" which would create 10 groups: [('a',1), ('e',1), ('i',1), ('o',1), ('u',1), ('a',1), ('e',1), ('i',1), ('o',1), ('u',1)]. When checking groups at index 3, we'd examine [('o',1), ('u',1), ('a',1), ('e',1), ('i',1)], which doesn't form "aeiou" and isn't a valid beautiful substring.

The Solution: The current implementation correctly handles this by explicitly checking if the concatenated characters equal "aeiou". This ensures we only count substrings where the vowels appear in the exact required order.

Pitfall 2: Edge Case with Fewer Than 5 Groups

The Problem: If the input string creates fewer than 5 groups (e.g., "aaa" creates just 1 group, or "aaaeee" creates 2 groups), the loop condition range(len(grouped_chars) - 4) could cause issues if not handled properly.

Why This Happens: When len(grouped_chars) < 5, the expression len(grouped_chars) - 4 becomes negative or zero, making the range empty. While this doesn't cause an error (the loop simply doesn't execute), developers might not realize that this implicitly handles the case where no beautiful substring can exist.

The Solution: The current implementation correctly handles this edge case automatically. When there are fewer than 5 groups, the loop doesn't execute and returns 0, which is the correct answer since we need at least 5 distinct vowel segments to form a beautiful substring.

Pitfall 3: Misunderstanding the Grouping Logic

The Problem: Developers might incorrectly implement the grouping phase, especially the pointer movement logic. A common error is forgetting to move the outer pointer i to j after creating a group, causing infinite loops or incorrect groupings.

Incorrect Implementation Example:

while i < n:
    j = i
    while j < n and word[j] == word[i]:
        j += 1
    grouped_chars.append((word[i], j - i))
    i += 1  # WRONG: Should be i = j

Why This Happens: The increment i += 1 would cause overlapping counts and incorrect group boundaries. For "aaa", this would create three groups [('a', 3), ('a', 2), ('a', 1)] instead of one group [('a', 3)].

The Solution: Always set i = j after processing a group to ensure the next iteration starts at the first character of the next distinct vowel. This maintains non-overlapping, consecutive groups that accurately represent the original string structure.