查找包含所有元音字母且按顺序排列的最长字串
问题描述
给定一个仅包含英文元音字母的字符串，需要找出满足以下条件的最长"美丽"子字符串：
- 必须包含全部5个元音字母（a、e、i、o、u）至少一次
- 这些元音字母必须按照字典序升序排列（即所有a必须在e之前，所有e必须在i之前，以此类推）
例如，"aeiou"和"aaaaaaeiiiioou"都是美丽字符串，但"uaeio"、"aeoiu"和"aaaeeeooo"不是。
返回最长美丽子字符串的长度，如果不存在则返回0。子字符串是字符串中连续的字符序列。
解法一：压缩连续字符法
思路：将连续相同的字符压缩为单个字符，同时记录每个压缩字符的连续出现次数。当发现连续5个压缩字符恰好构成"aeiou"时，计算对应的实际长度。
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
# 压缩后的字符序列
compressed = []
# 对应位置的重复次数
repeat_count = []
for idx in range(len(word)):
# 新字符或与前一个字符不同时，添加到压缩序列
if idx == 0 or word[idx] != word[idx - 1]:
compressed.append(word[idx])
repeat_count.append(1)
else:
# 否则增加计数
repeat_count[-1] += 1
max_len = 0
# 检查每个可能的5字符窗口
for i in range(len(compressed) - 4):
if compressed[i:i + 5] == 'aeiou':
window_len = sum(repeat_count[i:i + 5])
max_len = max(max_len, window_len)
return max_len
解法二：双指针滑动窗口
思路：使用左右指针维护一个窗口，确保窗口内字符满足升序排列。当发现当前字符小于前一个字符（不满足升序）时，需要移动左指针重新开始。同时用集合跟踪窗口内出现的不同元音种类。
class Solution:
def longestBeautifulSubstring(self, word: str) -> int:
length = len(word)
if length < 5:
return 0
left = 0
right = 1
result = 0
vowel_set = set(word[0])
current_char = word[0]
while right < length:
# 当前字符小于前一个字符，破坏升序规则
if current_char > word[right]:
# 如果已有5种元音，计算当前窗口长度
if len(vowel_set) == 5:
result = max(result, right - left)
# 重置窗口起点
left = right
vowel_set.clear()
current_char = word[right]
vowel_set.add(word[right])
right += 1
# 处理末尾情况
if len(vowel_set) == 5:
result = max(result, right - left)
return result
关键要点
- 元音必须严格按a→e→i→o→u的顺序出现
- 压缩法通过减少搜索空间来提升效率
- 滑动窗口法需要特别注意边界条件和窗口重置的时机
