滑动窗口题目：定长子串中元音的最大数目

题目

标题和出处

标题：定长子串中元音的最大数目

出处：1456. 定长子串中元音的最大数目

难度

4 级

题目描述

要求

给定字符串 $\text{s}$ 和整数 $\text{k}$，返回字符串 $\text{s}$ 中长度为 $\text{k}$ 的子字符串中可能包含的最大元音字母数。

英语中的元音字母为 $\text{‘a’}$、$\text{‘e’}$、$\text{‘i’}$、$\text{‘o’}$、$\text{‘u’}$。

示例

示例 1：

输入：$\text{s = "abciiidef", k = 3}$
输出：$\text{3}$
解释：子字符串 $\text{"iii"}$ 包含 $\text{3}$ 个元音字母。

示例 2：

输入：$\text{s = "aeiou", k = 2}$
输出：$\text{2}$
解释：任意长度为 $\text{2}$ 的子字符串都包含 $\text{2}$ 个元音字母。

示例 3：

输入：$\text{s = "leetcode", k = 3}$
输出：$\text{2}$
解释：$\text{"lee"}$、$\text{"eet"}$ 和 $\text{"ode"}$ 都包含 $\text{2}$ 个元音字母。

数据范围

• $\text{1}\le \text{s.length}\le {\text{10}}^{\text{5}}$
• $\text{s}$ 由小写英语字母组成
• $\text{1}\le \text{k}\le \text{s.length}$

解法

思路和算法

为了得到字符串 $s$ 的长度为 $k$ 的子字符串中可能包含的最大元音字母数，需要遍历每个长度为 $k$ 的子字符串，计算子字符串中的元音字母数。

首先遍历下标范围 $[0,k-1]$ 的子字符串并计算元音字母数。对于 $i\ge k$，当子字符串的下标范围从 $[i-k,i-1]$ 变成 $[i-k+1,i]$ 时，$s[i-k]$ 移出子字符串，$s[i]$ 移入子字符串，按照以下两步依次更新子字符串中的元音字母数。

1. 如果 $s[i-k]$ 是元音字母，则子字符串中的元音字母数减 $1$，否则子字符串中的元音字母数不减 $1$。

2. 如果 $s[i]$ 是元音字母，则子字符串中的元音字母数加 $1$，否则子字符串中的元音字母数不加 $1$。

遍历结束之后，即可得到每个长度为 $k$ 的子字符串中的元音字母数，以及最大元音字母数。

代码

class Solution {public int maxVowels(String s, int k) {int count = 0;int length = s.length();for (int i = 0; i < k; i++) {if (isVowel(s.charAt(i))) {count++;}}int maxCount = count;for (int i = k; i < length; i++) {if (isVowel(s.charAt(i - k))) {count--;}if (isVowel(s.charAt(i))) {count++;}maxCount = Math.max(maxCount, count);}return maxCount;}public boolean isVowel(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';}
}

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是字符串 $s$ 的长度。需要遍历字符串一次。

• 空间复杂度：$O(1)$。