Formatted question description: https://leetcode.ca/all/1839.html

1839. Longest Substring Of All Vowels in Order

Level

Medium

Description

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 * 10^5
  • word consists of characters 'a', 'e', 'i', 'o', and 'u'.

Solution

Create a string buffer to merge the same adjacent characters, and use a list to store the indices of each character, where the first index of 'a' and the last indices of the other letters are stored. Then loop over the string buffer. If there are five adjacent letters equal to "aeiou", then use the indices to calculate the length of the substring. Maintain the maximum length during the process. Finally, return the maximum length.

class Solution {
    public int longestBeautifulSubstring(String word) {
        int maxLength = 0;
        int length = word.length();
        StringBuffer sb = new StringBuffer();
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            char c = word.charAt(i);
            if (c == 'a') {
                if (i > 0 && c == word.charAt(i - 1))
                    continue;
                else {
                    sb.append(c);
                    list.add(i);
                }
            } else {
                if (i < length - 1 && c == word.charAt(i + 1))
                    continue;
                else {
                    sb.append(c);
                    list.add(i);
                }
            }
        }
        int newLength = sb.length();
        for (int i = 4; i < newLength; i++) {
            if (sb.charAt(i - 4) == 'a' && sb.charAt(i - 3) == 'e' && sb.charAt(i - 2) == 'i' && sb.charAt(i - 1) == 'o' && sb.charAt(i) == 'u') {
                int start = list.get(i - 4), end = list.get(i);
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
        return maxLength;
    }
}

All Problems

All Solutions