1456. 定长子串中元音的最大数目 #
- 标签:字符串、滑动窗口
- 难度:中等
题目大意 #
给定字符串 s
和整数 k
。
要求:返回字符串 s
中长度为 k
的单个子字符串中可能包含的最大元音字母数。
注意:英文中的元音字母为(a
, e
, i
, o
, u
)。
解题思路 #
固定长度的滑动窗口题目。维护一个长度为 k
的窗口,并统计滑动窗口中最大元音字母数。具体做法如下:
ans
用来维护长度为k
的单个字符串中最大元音字母数。window_count
用来维护窗口中元音字母数。集合vowel_set
用来存储元音字母。left
、right
都指向字符串s
的第一个元素,即:left = 0
,right = 0
。- 判断
s[right]
是否在元音字母集合中,如果在则用window_count
进行计数。 - 当窗口元素个数为
k
时,即:right - left + 1 >= k
时,更新ans
。然后判断s[left]
是否为元音字母,如果是则window_count -= 1
,并向右移动left
,从而缩小窗口长度,即left += 1
,使得窗口大小始终保持为k
。 - 重复 3 ~ 4 步,直到
right
到达数组末尾。 - 最后输出
ans
。
代码 #
|
|