Longest Substring Of All Vowels in Order — LeetCode 1839 Python Solution

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

Example

Input

word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"

Output

13

Explanation

The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.

Python solution

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

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1839. Longest Substring Of All Vowels in Order is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems