Welcome to Subscribe On Youtube

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;
    }
}

############

class Solution {
    public int longestBeautifulSubstring(String word) {
        int n = word.length();
        List<Node> arr = new ArrayList<>();
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && word.charAt(j) == word.charAt(i)) {
                ++j;
            }
            arr.add(new Node(word.charAt(i), j - i));
            i = j;
        }
        int ans = 0;
        for (int i = 0; i < arr.size() - 4; ++i) {
            Node a = arr.get(i), b = arr.get(i + 1), c = arr.get(i + 2), d = arr.get(i + 3),
                 e = arr.get(i + 4);
            if (a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u') {
                ans = Math.max(ans, a.v + b.v + c.v + d.v + e.v);
            }
        }
        return ans;
    }
}

class Node {
    char c;
    int v;

    Node(char c, int v) {
        this.c = c;
        this.v = v;
    }
}

  • // OJ: https://leetcode.com/problems/longest-substring-of-all-vowels-in-order/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int longestBeautifulSubstring(string s) {
        int i = 0, N = s.size(), ans = 0;
        string ch = "aeiou";
        while (i < N) {
            int start = i;
            bool valid = true;
            for (char c : ch) {
                int j = i;
                while (i < N && s[i] == c) ++i;
                valid = i > j;
                if (!valid) break;
            }
            if (valid) ans = max(ans, i - start);
            while (i < N && s[i] != 'a') ++i;
        }
        return ans;
    }
};

  • 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

############

# 1839. Longest Substring Of All Vowels in Order
# https://leetcode.com/problems/longest-substring-of-all-vowels-in-order/

class Solution:
    def longestBeautifulSubstring(self, word: str) -> int:
        if "a" not in word: return 0
        v = ["a", "e", "i", "o", "u"]

        vi = 0
        n = len(word)
        curr = res = 0
        i = j = word.index("a")
        while j < n and word[j] == "a":
            j += 1
        vi += 1

        while i < n and j < n:
            if word[j] != v[vi]:
                vi = 0
                i = j
                
                while j < n and word[j] != v[vi]:
                    j += 1
                i = j

            if j >= n: return res
            
            while j < n and word[j] == v[vi]:
                j += 1
            
            vi += 1
            if vi == 5: 
                res = max(res, j - i)
                vi = 0
                i = j
            
        return res


  • func longestBeautifulSubstring(word string) (ans int) {
	arr := []pair{}
	n := len(word)
	for i := 0; i < n; {
		j := i
		for j < n && word[j] == word[i] {
			j++
		}
		arr = append(arr, pair{word[i], j - i})
		i = j
	}
	for i := 0; i < len(arr)-4; i++ {
		a, b, c, d, e := arr[i], arr[i+1], arr[i+2], arr[i+3], arr[i+4]
		if a.c == 'a' && b.c == 'e' && c.c == 'i' && d.c == 'o' && e.c == 'u' {
			ans = max(ans, a.v+b.v+c.v+d.v+e.v)
		}
	}
	return
}

type pair struct {
	c byte
	v int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions