LeetCode 1839: Longest Substring Of All Vowels in Order

Explanation

To solve this problem, we can iterate through the input string and maintain a sliding window that contains all the vowels in alphabetical order. We can keep track of the current vowel being considered and the count of each vowel encountered so far. Whenever we encounter a vowel that is not in the correct order, we reset the window to start from the current vowel. We update the maximum beautiful substring length whenever we find a valid beautiful substring.

Algorithm:

1. Initialize variables: maxLen (maximum beautiful substring length), currLen (current beautiful substring length), currVowelIndex (index of the current vowel in the alphabetical order).
2. Iterate through the input string: a. If the current character is the next vowel in alphabetical order, increment currLen, update currVowelIndex, and update the count of the current vowel. b. If the current character is the same as the current vowel, increment currLen. c. If the current character is a vowel but not in the correct order, reset currLen to 1 and update currVowelIndex. d. If the current substring is beautiful, update maxLen if currLen is greater.
3. Return maxLen.

Time Complexity: O(N), where N is the length of the input string. Space Complexity: O(1)

class Solution {
    public int longestBeautifulSubstring(String word) {
        int maxLen = 0, currLen = 1, currVowelIndex = 0;
        int[] count = new int[5];
        count[word.charAt(0) - 'a']++;

        for (int i = 1; i < word.length(); i++) {
            char currChar = word.charAt(i);
            char prevChar = word.charAt(i - 1);

            if (currChar == prevChar) {
                currLen++;
            } else if (currChar == "aeiou".charAt(currVowelIndex + 1)) {
                currLen++;
                currVowelIndex++;
            } else if (currChar == 'a') {
                currLen = 1;
                currVowelIndex = 0;
                count = new int[5];
                count[0]++;
            } else {
                currLen = 1;
                currVowelIndex = 0;
                count = new int[5];
                count[currChar - 'a']++;
            }

            if (currVowelIndex == 4) {
                maxLen = Math.max(maxLen, currLen);
            }

            count[currChar - 'a']++;
        }

        return maxLen;
    }
}