class Solution {
public:
int longestBeautifulSubstring(string word) {
}
};
1839. 所有元音按顺序排布的最长子字符串
当一个字符串满足如下条件时，我们称它是 美丽的 ：
'a' ，'e' ，'i' ，'o' ，'u'）都必须 至少 出现一次。'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）比方说，字符串 "aeiou" 和 "aaaaaaeiiiioou" 都是 美丽的 ，但是 "uaeio" ，"aeoiu" 和 "aaaeeeooo" 不是美丽的 。
给你一个只包含英文元音字母的字符串 word ，请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0 。
子字符串 是字符串中一个连续的字符序列。
示例 1：
输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu" 输出：13 解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。
示例 2：
输入：word = "aeeeiiiioooauuuaeiou" 输出：5 解释：最长子字符串是 "aeiou" ，长度为 5 。
示例 3：
输入：word = "a" 输出：0 解释：没有美丽子字符串，所以返回 0 。
提示：
1 <= word.length <= 5 * 105word 只包含字符 'a'，'e'，'i'，'o' 和 'u' 。原站题解
golang 解法, 执行用时: 120 ms, 内存消耗: 7.2 MB, 提交时间: 2022-12-11 12:49:05
var re = regexp.MustCompile("a+e+i+o+u+")
func longestBeautifulSubstring(s string) (ans int) {
for _, t := range re.FindAllString(s, -1) {
if len(t) > ans {
ans = len(t)
}
}
return
}
golang 解法, 执行用时: 24 ms, 内存消耗: 7 MB, 提交时间: 2022-12-11 12:48:52
func longestBeautifulSubstring(s string) (ans int) {
const vowel = "aeiou"
cur, sum := 0, 0
for i, n := 0, len(s); i < n; {
start := i
ch := s[start]
for i < n && s[i] == ch {
i++
}
if ch != vowel[cur] {
cur, sum = 0, 0
if ch != vowel[0] {
continue
}
}
sum += i - start
cur++
if cur == 5 {
if sum > ans {
ans = sum
}
cur, sum = 0, 0
}
}
return
}
java 解法, 执行用时: 48 ms, 内存消耗: 47.7 MB, 提交时间: 2022-12-11 12:48:31
/**
* 思路：判断字符种类和大小
* 这5个元音字符是升序的且字符串中仅包含这些元音字母，
* 所以当字符串满足整体升序的同时字符种类达到5,那么这个字符串就是美丽的。
**/
class Solution {
public int longestBeautifulSubstring(String word) {
int ans = 0, type = 1, len = 1;
for(int i = 1; i < word.length(); i++){
if(word.charAt(i) >= word.charAt(i-1)) len++; //更新当前字符串长度
if(word.charAt(i) > word.charAt(i-1)) type++; //更新当前字符种类
if(word.charAt(i) < word.charAt(i-1)) { type = 1; len = 1;} //当前字符串不美丽，从当前字符重新开始
if(type == 5) ans = Math.max(ans, len); //更新最大字符串
}
return ans;
}
}
cpp 解法, 执行用时: 68 ms, 内存消耗: 26.2 MB, 提交时间: 2022-12-11 12:47:16
/**
* 1.首先如果数组长度小于5的话，不可能满足美丽的定义，将这种情况提前排除
* 2.遍历时分了几种情况判断：
* - 如果当前字符比上一个不小（顺序意义），那么当前子串长度+1
* - 如果当前字符比上一个大，那么子串中元音字母种类+1
* - 如果当前字符比上一个小，那么肯定当前字串不美丽，以当前字符为首继续进行遍历
* 3.如果当前子字符串没有以a开头的话，那么在进行下一个子字符串开始遍历之前，元音种类一定不会达到5，所以只要判断种类即可
* 4.当元音种类为5的时候，持续维护更新最终结果，取出最大值即可
**/
class Solution {
public:
int longestBeautifulSubstring(string word) {
if (word.size()<5)return 0;
int res=0;
int rlen=1;
int vowel=1;
for(int i=1;i<word.length();i++){
if(word[i]>=word[i-1])rlen++;
if(word[i]>word[i-1])vowel++;
if(word[i]<word[i-1]){rlen=1;vowel=1;}
if(vowel==5){res=rlen>res?rlen:res;}
}
return res;
}
};
python3 解法, 执行用时: 660 ms, 内存消耗: 17.5 MB, 提交时间: 2022-12-11 12:45:59
class Solution:
TRANSIT = {
("a", "e"), ("e", "i"), ("i", "o"), ("o", "u"),
("a", "a"), ("e", "e"), ("i", "i"), ("o", "o"), ("u", "u"),
("x", "a"), ("e", "a"), ("i", "a"), ("o", "a"), ("u", "a"),
}
def longestBeautifulSubstring(self, word: str) -> int:
cur, ans = 0, 0
status = "x"
for ch in word:
if (status, ch) in Solution.TRANSIT:
if status != "a" and ch == "a":
cur = 1
else:
cur = cur + 1
status = ch
else:
cur = 0
status = "x"
if status == "u":
ans = max(ans, cur)
return ans