Maximum Number of Vowels In a Substring Of Given Length

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

分析

定义一个固定长度为 k 的窗口，用变量 cur 记录窗口内的元音字母数量
遍历字符串 s
- 当加入一个新字符时，若其为元音，则增加 cur
- 若窗口大小超过 k，移除窗口左端字符，若其为元音，则减少 cur
- 在窗口大小达到 k 时，更新最大元音数量 res
遍历结束后，返回结果

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution
{
public:
    int maxVowels(string s, int k)
    {
        std::unordered_set<char> hash = {'a', 'e', 'i', 'o', 'u'}; // 元音集合
        int res = 0, cur = 0; // res: 最大元音数量, cur: 当前窗口元音数量
        for (int i = 0, j = 0; i < s.size(); ++i)
        {
            if (hash.count(s[i])) // 判断当前字符是否为元音
                ++cur;
            if (i - j + 1 > k) // 如果窗口超过长度 k
            {
                if (hash.count(s[j])) // 窗口左端字符是否为元音
                    --cur;
                ++j; // 移动左端
            }
            if (i >= k - 1) // 当窗口长度达到 k 时，更新结果
                res = std::max(res, cur);
        }
        return res;
    }
};