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

题目描述#

给你字符串 s 和整数 k。

请你在字符串 s 中找到长度为 k 的子串，使得子串中元音字母（a, e, i, o, u）的数目最大，并返回该最大值。

示例 1：

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

示例 2：

1
输入：s = "aeiou", k = 2
2
输出：2

示例 3：

1
输入：s = "leetcode", k = 3
2
输出：2

提示：

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

解法思路#

定长滑动窗口，核心思想是：维护一个长度为 k 的窗口，统计窗口内元音个数，滑动时只考虑离开窗口的字母和进入窗口的字母，中间字母无需重复统计，从而把每步更新降到 O(1)。

暴力枚举所有子串要 O(nk)，而向右滑一个位置时，只需：

移除离开窗口的字母 s[i-k]，是元音则计数 -1；
加入进入窗口的字母 s[i]，是元音则计数 +1。

定长滑窗统一三步套路（入-更新答案-出）：

入：枚举右端点 i，把 s[i] 计入窗口元音数。若左端点 i-k+1 < 0，说明窗口长度不足 k（尚未形成第一个窗口），继续下一步循环。
更新答案：此时窗口长度为 k，用当前元音数更新答案最大值。
出：把左端点 i-k+1 处元素移出窗口，更新元音数，为下一轮做准备。

逐步举例（s = "abciiidef", k = 3，用 vowel 表示当前窗口元音数）：

从左到右遍历。先统计前 k-1=2 个字母 a, b 的元音数：vowel = 1。
i=2，c 进入窗口 → 窗口 abc，vowel = 1，得第 1 个长 k 子串，更新 ans = 1；出 a → vowel = 0。
i=3，i 进入窗口 → 窗口 bci，vowel = 1，更新 ans = 1；出 b → vowel = 1。
i=4，i 进入窗口 → 窗口 cii，vowel = 2，更新 ans = 2；出 c → vowel = 2。
i=5，i 进入窗口 → 窗口 iii，vowel = 3，更新 ans = 3；出 i → vowel = 2。
i=6，d 进入窗口 → 窗口 iid，vowel = 2，更新 ans 仍为 3；出 i → vowel = 1。
i=7，e 进入窗口 → 窗口 ide，vowel = 2；出 i → vowel = 1。
i=8，f 进入窗口 → 窗口 def，vowel = 1。

遍历结束，ans = 3，与预期一致。可以看到每步只处理进/出窗口的 2 个字符，窗口内其余元素不重复统计。

优化：答案的理论最大值就是 k（窗口内全是元音）。一旦 ans == k，答案无法再增大，可直接提前退出循环，进一步减少遍历。

代码见下方。关于外围的 set/直接 in "aeiou" 判断元音的写法、以及”入-更新-出”三步边界条件，参考灵茶山艾府对该题（也是定长滑窗模板题）的完整讲解。

复杂度分析#

时间复杂度：O(n)，其中 n 是 s 的长度，每步滑动 O(1)。
空间复杂度：O(1)，仅使用常数额外空间。

代码实现#

1
class Solution:
2
    def maxVowels(self, s: str, k: int) -> int:
3
        vowels = set("aeiou")
4
        cur = sum(1 for c in s[:k] if c in vowels)
5
        ans = cur
6
        for i in range(k, len(s)):
7
            cur += (s[i] in vowels) - (s[i - k] in vowels)
8
            if cur > ans:
9
                ans = cur
10
        return ans

1
import unittest
2

3

4
class TestMaxVowels(unittest.TestCase):
5
    def setUp(self):
6
        self.solution = Solution()
7

8
    def test_example1(self):
9
        self.assertEqual(self.solution.maxVowels("abciiidef", 3), 3)
10

11
    def test_example2(self):
12
        self.assertEqual(self.solution.maxVowels("aeiou", 2), 2)
13

14
    def test_example3(self):
15
        self.assertEqual(self.solution.maxVowels("leetcode", 3), 2)
16

17
    def test_single_char(self):
18
        self.assertEqual(self.solution.maxVowels("a", 1), 1)
19

20
    def test_no_vowel(self):
21
        self.assertEqual(self.solution.maxVowels("bcdfg", 2), 0)
22

23

24
if __name__ == "__main__":
25
    unittest.main()