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

🟠   🔖  字符串 滑动窗口  🔗 力扣 LeetCode

题目

Given a string s and an integer k, return the maximum number of vowel letters in any substring ofs with lengthk.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Example 1:

Input: s = "abciiidef", k = 3

Output: 3

Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2

Output: 2

Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3

Output: 2

Explanation: "lee", "eet" and "ode" contain 2 vowels.

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= s.length

题目大意

给你字符串 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

解题思路

1. 定义元音判断函数：使用 isVowel 函数检查字符是否为元音；
2. 初始化计数：设置当前元音计数 count 和最大元音计数 max；
3. 滑动窗口：
   • 使用滑动窗口来维护当前窗口内的元音字母计数；
   • 窗口大小固定为 k，在遍历字符串时，动态更新窗口内的元音计数 count；
   • 在每次迭代中，如果当前字符是元音，则增加计数；
   • 当索引 i 大于等于 k 时，减去窗口左侧的字符（即 s[i - k]）的元音计数，以保持窗口的大小；
4. 更新最大计数：在当前索引 i 大于 k - 1 时，检查并更新最大元音计数 max。
5. 返回结果：最终返回找到的最大元音计数；

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，只需遍历字符串一次。
• 空间复杂度：O(1)，只使用常量空间来存储计数和最大值。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var maxVowels = function (s, k) {
	const isVowel = (char) => 'aeiou'.indexOf(char) !== -1;

	let count = 0,
		max = 0;
	for (let i = 0; i < s.length; i++) {
		if (isVowel(s[i])) {
			count++; // 增加当前字符的元音计数
		}
		if (i >= k && isVowel(s[i - k])) {
			count--; // 移除窗口左侧字符的元音计数
		}
		if (i >= k - 1) {
			max = Math.max(max, count); // 更新最大元音计数
		}
	}
	return max; // 返回最大元音计数
};

相关题目

题号	标题	题解	标签	难度
2271	毯子覆盖的最多白色砖块数		贪心 数组 二分查找 2+
2379	得到 K 个黑块的最少涂色次数		字符串 滑动窗口
2414	最长的字母序连续子字符串的长度		字符串