LC1456. 定长子串中元音的最大数目

题目描述

给你字符串 s 和整数 k 。 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为（a, e, i, o, u）。 示例 1： 输入：s = "abciiidef", k = 3 输出：3 解释：子字符串 "iii" 包含 3 个元音字母。 示例 2： 输入：s = "aeiou", k = 2 输出：2 解释：任意长度为 2 的子字符串都包含 2 个元音字母。 示例 3： 输入：s = "leetcode", k = 3 输出：2 解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。 示例 4： 输入：s = "rhythms", k = 4 输出：0 解释：字符串 s 中不含任何元音字母。 示例 5： 输入：s = "tryhard", k = 4 输出：1

提示： 1 <= s.length <= 10^5 s 由小写英文字母组成 1 <= k <= s.length

题目解析

好的，没问题。我们一起来把这道题讲明白。

题目在说什么

简单说，就是给你一个字符串 s，比如 "abciiidef"，再给你一个固定的长度 k，比如 3。你需要在这个字符串里，找所有长度为 k 的连续片段（专业说法叫“子串”），然后数一数每个片段里有多少个元音字母（a, e, i, o, u）。最后，我们要找出这些片段里，元音字母数量最多的那个是多少。

举个例子，"abciiidef" 长度是3的片段有：

• "abc"：元音只有 a，1个。
• "bci"：元音只有 i，1个。
• "cii"：元音有 i 和 i，2个。
• "iii"：元音有 i、i、i，3个。
• "iid"：元音有 i、i，2个。
• "ide"：元音有 i、e，2个。
• "def"：元音只有 e，1个。

所以最多的是3个，答案就是3。

思路是怎么来的

想象一下，你有一个很长的队伍，队伍里的人身上都贴着一个字母。你想看连续 k 个人组成的小组里，有多少人贴的是元音字母。

最笨的办法是什么？就是像上面那样，把每个长度为 k 的小组都单独数一遍。从第1个人开始数前 k 个，然后从第2个人开始再数一遍前 k 个……这样很慢，因为每次都要重新数一遍，做了很多重复劳动。

那有没有聪明一点的办法呢？有的。我们可以用一个“滑动窗口”的思路。

生活比喻： 想象你有一个长度为 k 的“魔法框”。一开始，你把框放在队伍的最左边，框住前 k 个人。你数一下框里有几个元音，记下来。

然后，你想看下一组（从第2个人开始的那组）。你不需要把框拿起来重新去框第2到第 k+1 个人。你只需要把框向右滑动 一格。

滑动一格会发生什么？ 1. 框的 最左边 有一个人出去了（他离开了框的范围）。 2. 框的 最右边 有一个人进来了（他进入了框的范围）。

所以，新的小组的元音数量，跟旧的小组的元音数量有什么关系呢？

• 如果出去的那个人是元音，那么新小组的元音数就要 减1。
• 如果进来的那个人是元音，那么新小组的元音数就要 加1。
• 如果出去或进来的人不是元音，那元音数就不变。

这样，我们每次只需要处理“出去”和“进来”的两个人，而不用重新数整个框里的所有人。是不是快多了？

我们只需要做一次完整的计数（数第一个小组），然后后面每次滑动一格，更新一下计数，并记录下看到的最大值就行了。

代码逐步拆解

我们来看看用 Python 怎么写。我会把代码拆成小块，每一块都告诉你它在干嘛。

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        # 第一步：准备一个“元音集合”，方便快速判断一个字母是不是元音
        vowels = set('aeiou')
        
        # 第二步：先数一下第一个窗口（前 k 个字符）里的元音数量
        # 用一个变量 current_count 来记录当前窗口的元音数
        current_count = 0
        for i in range(k):
            if s[i] in vowels:
                current_count += 1
        
        # 第三步：把第一个窗口的元音数，作为目前看到的最大值
        max_count = current_count
        
        # 第四步：开始滑动窗口
        # 窗口从索引 0 到 k-1，现在我们要滑动它，让窗口变成从索引 1 到 k
        # 所以我们要用一个循环，让窗口的右边界从 k 一直走到字符串末尾
        # 循环变量 i 代表新窗口的右边界索引
        for i in range(k, len(s)):
            # 新窗口的右边界是 i，新进来的字符是 s[i]
            # 新窗口的左边界是 i-k+1，但我们要关心的是“出去”的字符，它是旧窗口的左边界，也就是 s[i-k]
            
            # 检查新进来的字符 s[i] 是不是元音
            if s[i] in vowels:
                current_count += 1
            
            # 检查出去的字符 s[i-k] 是不是元音
            if s[i-k] in vowels:
                current_count -= 1
            
            # 更新最大元音数
            # 看看当前窗口的元音数 current_count 是不是比之前记录的最大值还大
            max_count = max(max_count, current_count)
        
        # 第五步：返回找到的最大值
        return max_count

关键步骤解释：

1. `vowels = set('aeiou')`：为什么用集合？因为 s[i] in vowels 这个判断在集合里非常快，是 O(1) 的。如果用列表，就会慢一些。