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 _thelength of the longest beautiful substring of _word . If no such substring exists, return0.

A substring is a contiguous sequence of characters in a string.

Examples

Example 1

1
2
3

Input: word = "aeiaaio _aaaaeiiiiouuu_ ooaauuaeiu"
Output: 13
Explanation: The longest beautiful substring in word is "aaaaeiiiiouuu" of length 13.

Example 2

1
2
3

Input: word = "aeeeiiiioooauuu _aeiou_ "
Output: 5
Explanation: The longest beautiful substring in word is "aeiou" of length 5.

Example 3

1
2
3

Input: word = "a"
Output: 0
Explanation: There is no beautiful substring, so return 0.

Constraints

  • 1 <= word.length <= 5 * 10^5
  • word consists of characters 'a', 'e', 'i', 'o', and 'u'.

Solution

Method 1 – Sliding Window

Intuition

We want the longest substring containing all five vowels in order, with each vowel appearing at least once and all ‘a’s before ’e’s, all ’e’s before ‘i’s, etc. We can use a sliding window to expand as long as the order is maintained, and reset when the order breaks.

Approach

  1. Map each vowel to its order: ‘a’→0, ’e’→1, ‘i’→2, ‘o’→3, ‘u’→4.
  2. Use two pointers to define a window. Expand the window as long as the current vowel is not less than the previous vowel.
  3. Track the number of unique vowels in the window.
  4. If all 5 vowels are present in order, update the answer.
  5. Reset the window when the order breaks.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int longestBeautifulSubstring(string word) {
        int n = word.size(), ans = 0, cnt = 1, start = 0;
        for (int i = 1; i < n; ++i) {
            if (word[i] < word[i-1]) {
                cnt = 1;
                start = i;
            } else if (word[i] > word[i-1]) {
                cnt++;
            }
            if (cnt == 5) ans = max(ans, i - start + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func longestBeautifulSubstring(word string) int {
    n, ans, cnt, start := len(word), 0, 1, 0
    for i := 1; i < n; i++ {
        if word[i] < word[i-1] {
            cnt = 1
            start = i
        } else if word[i] > word[i-1] {
            cnt++
        }
        if cnt == 5 {
            if i-start+1 > ans {
                ans = i - start + 1
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int longestBeautifulSubstring(String word) {
        int n = word.length(), ans = 0, cnt = 1, start = 0;
        for (int i = 1; i < n; ++i) {
            if (word.charAt(i) < word.charAt(i-1)) {
                cnt = 1;
                start = i;
            } else if (word.charAt(i) > word.charAt(i-1)) {
                cnt++;
            }
            if (cnt == 5) ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun longestBeautifulSubstring(word: String): Int {
        val n = word.length
        var ans = 0
        var cnt = 1
        var start = 0
        for (i in 1 until n) {
            if (word[i] < word[i-1]) {
                cnt = 1
                start = i
            } else if (word[i] > word[i-1]) {
                cnt++
            }
            if (cnt == 5) ans = maxOf(ans, i - start + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        n = len(word)
        ans = cnt = 0
        start = 0
        for i in range(1, n):
            if word[i] < word[i-1]:
                cnt = 1
                start = i
            elif word[i] > word[i-1]:
                cnt += 1
            if cnt == 5:
                ans = max(ans, i - start + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn longest_beautiful_substring(word: String) -> i32 {
        let s = word.as_bytes();
        let n = s.len();
        let mut ans = 0;
        let mut cnt = 1;
        let mut start = 0;
        for i in 1..n {
            if s[i] < s[i-1] {
                cnt = 1;
                start = i;
            } else if s[i] > s[i-1] {
                cnt += 1;
            }
            if cnt == 5 {
                ans = ans.max((i - start + 1) as i32);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    longestBeautifulSubstring(word: string): number {
        const n = word.length;
        let ans = 0, cnt = 1, start = 0;
        for (let i = 1; i < n; ++i) {
            if (word[i] < word[i-1]) {
                cnt = 1;
                start = i;
            } else if (word[i] > word[i-1]) {
                cnt++;
            }
            if (cnt === 5) ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan the string once.
  • 🧺 Space complexity: O(1), as we use only a few variables.