静态网页模板免费下载网站,外部调用wordpress函数,网站模板下载模板下载安装,买个域名题目描述
给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。英文中的 元音字母 为#xff08;a, e, i, o, u#xff09;。示例 1#xff1a;输入#xff1a;s abciiidef, k 3
输出#xff1a;3
解释#xf…题目描述
给你字符串 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来源力扣LeetCode
链接https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。思路
看到题目第一个想法就是滑动窗口了因为子字符串的长度 k 是固定的所以真的很简单。
使用一个长度为 k 的窗口从 s 的左侧滑向右侧分别计算窗口中包含的元音个数最终返回最大值
要点是如何计算窗口中的元音个数如果窗口每移动一步就遍历计算一次必然是超时的。
其实仔细想想窗口每次移动时其中包含的元素只有两个变化
窗口左侧丢弃了一个元素窗口右侧新增了一个元素
那这样我们只需要在滑动开始时记录一下窗口中的元音个数 count之后移动窗口时判断左侧丢弃的元素和右侧新增的元素是不是元音对应地减少或者增加 count 就行。 复杂度
时间复杂度$O(N)$N 为字符串的长度。空间复杂度$O(1)$。
代码
/*** param {string} s* param {number} k* return {number}*/
var maxVowels function (s, k) {const vowels new Set([a, e, i, o, u]);let count 0,l 0,r 0;while (r k) {vowels.has(s[r]) count;r;}let max count;while (r s.length) {vowels.has(s[r]) count;vowels.has(s[l]) count--;l;r;max Math.max(max, count);}return max;
};
