此题解采用了滑动窗口的策略来寻找包含所有五个元音至少各一次的最长子字符串。首先,我们使用三个指针 start, left 和 right 来定义当前探索的子字符串。我们从左到右遍历字符串,使用一个计数器来统计各个元音字母的出现次数。当我们遇到一个非元音字符时,我们将清空计数器并将 start 移动到 right 的位置。如果在 right 指针的位置我们发现所有五个元音都至少出现一次,我们就尝试从 left 开始减少窗口的大小直到不满足条件为止。这个过程中,我们计算从 start 到 left-1 所有可能的元音子字符串的数量并累加到结果中。每找到一个有效的子字符串后,我们调整 left 指针并尝试寻找新的子字符串。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def countVowelSubstrings(self, word: str) -> int:
counter = Counter() # 创建计数器用于统计元音
n = len(word)
start = left = right = 0 # 初始化三个指针
vowels = 'aeiou' # 元音字符集
res = 0 # 结果计数器
while right < n:
if start == right: # 寻找首个元音字符作为起点
while start < n:
if word[start] in vowels:
break
start += 1
left = start
right = start
while right < n: # 扩展 right 指针以包含所有元音
if word[right] not in vowels:
self.clear(counter)
break
counter[word[right]] += 1
right += 1
if self.all_vowels(counter): # 检查是否包含所有元音
break
if self.all_vowels(counter): # 确认找到有效子字符串后,尝试减少窗口大小
while left < right:
counter[word[left]] -= 1
left += 1
if not self.all_vowels(counter):
break
res += left - start # 计算子字符串数量
left -= 1
counter[word[left]] += 1 # 调整计数器
else:
start = right # 非元音字符,重置窗口
return res
def all_vowels(self, counter):
for c in 'aeiou':
if counter[c] == 0: # 检查所有元音是否都至少出现一次
return False
return True
def clear(self, counter):
for c in 'aeiou': # 清空计数器
counter[c] = 0