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 * 105
word
consists of characters'a'
,'e'
,'i'
,'o'
, and'u'
.
Related Topics:
Two Pointers, String
// OJ: https://leetcode.com/problems/longest-substring-of-all-vowels-in-order/
// Author: github.com/lzl124631x
// 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;
}
};
// OJ: https://leetcode.com/problems/longest-substring-of-all-vowels-in-order/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int longestBeautifulSubstring(string s) {
int N = s.size(), cnt = 1, len = 1, ans = 0;
for (int i = 1; i != N; ++i) {
if (s[i - 1] == s[i]) ++len;
else if (s[i - 1] < s[i]) {
++len;
++cnt;
} else {
cnt = 1;
len = 1;
}
if (cnt == 5) ans = max(ans, len);
}
return ans;
}
};