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

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

  • 标签:字符串、滑动窗口
  • 难度:中等

题目大意 #

给定字符串 s 和整数 k

要求:返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

注意:英文中的元音字母为(a, e, i, o, u)。

解题思路 #

固定长度的滑动窗口题目。维护一个长度为 k 的窗口,并统计滑动窗口中最大元音字母数。具体做法如下:

  1. ans 用来维护长度为 k 的单个字符串中最大元音字母数。window_count 用来维护窗口中元音字母数。集合 vowel_set 用来存储元音字母。
  2. leftright 都指向字符串 s 的第一个元素,即:left = 0right = 0
  3. 判断 s[right] 是否在元音字母集合中,如果在则用 window_count 进行计数。
  4. 当窗口元素个数为 k 时,即:right - left + 1 >= k 时,更新 ans。然后判断 s[left] 是否为元音字母,如果是则 window_count -= 1,并向右移动 left,从而缩小窗口长度,即 left += 1,使得窗口大小始终保持为 k
  5. 重复 3 ~ 4 步,直到 right 到达数组末尾。
  6. 最后输出 ans

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        left, right = 0, 0
        ans = 0
        window_count = 0
        vowel_set = ('a','e','i','o','u')

        while right < len(s):
            if s[right] in vowel_set:
                window_count += 1

            if right - left + 1 >= k:
                ans = max(ans, window_count)
                if s[left] in vowel_set:
                    window_count -= 1
                left += 1

            right += 1
        return ans
本站总访问量  次  |  您是本站第  位访问者