1456. 定长子串中元音的最大数目-LeetCode

🎯 问题描述（来源于LeetCode）

描述：给你一个字符串 s 和一个整数 k，请你找出 s 中的最长子串，该子串包含的元音字母数不超过 k 个。返回这个子串的长度。

说明：

元音字母为 ‘a’, ‘e’, ‘i’, ‘o’, ‘u’（仅小写）
子串是字符串中连续的字符序列
$1 <= s.length <= 10^5$
$1 <= k <= s.length$
示例：
- 示例 1：

1
2
3

输入：s = "abciiidef", k = 3
输出：3
解释：子串 "iii" 包含 3 个元音字母

- **示例 2**：

1
2
3

输入：s = "aeiou", k = 2
输出：2
解释：任何长度为 2 的子串都包含 2 个元音字母

- **示例 3**：

1
2
3

输入：s = "leetcode", k = 3
输出：2
解释："lee" 和 "eet" 都包含 3 个元音字母，但长度为 2

💻 解题思路

思路1：滑动窗口

核心思想：
这是一个典型的固定长度滑动窗口问题。我们需要在字符串 s 中找到长度为 k 的子串，并计算其中元音字母的数量。

窗口定义：维护一个长度为 k 的滑动窗口
统计策略：
- 从左到右遍历字符串，将当前字符加入窗口
- 如果当前字符是元音字母，计数器加1
- 当窗口长度达到 k 时，更新最大值
- 将窗口最左边的字符移出窗口，如果它是元音字母，计数器减1

算法步骤：

初始化答案 ans 和当前窗口元音数 v_num 为0
遍历字符串每个位置 i：
- 如果当前字符是元音字母，v_num 加1
- 计算窗口左边界 left = i - k + 1
- 如果左边界 >= 0，说明窗口已满：
  - 更新最大值 ans = max(ans, v_num)
  - 如果左边界字符是元音字母，v_num 减1（滑动窗口）
返回 ans

思路1：代码实现

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        ans = v_num = 0
        for i, st in enumerate(s):
            # 如果当前字符是元音字母，计数器加1
            if st in "aeiou":
                v_num += 1
            
            # 计算窗口左边界
            left = i - k + 1
            
            # 如果左边界 >= 0，说明窗口已满
            if left < 0:
                continue
            
            # 更新最大值
            ans = max(ans, v_num)
            
            # 如果左边界字符是元音字母，计数器减1
            if s[left] in "aeiou":
                v_num -= 1
        
        return ans

思路1：📊 性能分析

提交结果

运行时间：71ms击败56.24%
内存消耗：19.71MB击败22.58%

复杂度验证

时间复杂度： $O(N)$ $O (N)$
- 解析：只需要遍历字符串一次，每个字符最多被访问两次（加入和移出窗口）
空间复杂度： $O(1)$ $O (1)$
- 解析：只使用了常数个额外变量

思考

为什么使用 left = i - k + 1 来判断窗口？
- 这是固定长度滑动窗口的经典写法。当 i（当前右边界）达到 k-1 时，left 变为0，窗口正好包含 k 个元素。
- 例如：k=3，当 i=2 时，left=0，窗口包含索引 0,1,2 的字符。
窗口滑动的逻辑：
- 当窗口填满后，每次向右移动一格，需要将最左边的元素移出窗口。
- 通过检查 s[left] 是否为元音字母来决定是否减少计数器。
优化空间：
- 代码已经非常简洁，时间复杂度最优。
- 可以提前返回的情况：如果某个窗口的元音数已经达到 k，且 k 是最大可能值，可以直接返回 k。
边界处理：
- 使用 `left