Medium

题目描述

给定字符串 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 个元音字母。

提示：

  • 1 <= s.length <= 10^5
  • s 由小写英文字母组成
  • 1 <= k <= s.length

解题思路

这是一道典型的滑动窗口问题。我们需要在字符串中找到长度为 k 的子字符串，使其包含的元音字母数量最多。

核心思路：

  1. 使用固定大小的滑动窗口，窗口大小为 k
  2. 维护当前窗口中元音字母的数量
  3. 滑动窗口时，移除左边字符，添加右边字符，动态更新元音数量
  4. 记录过程中的最大元音数量

算法步骤：

  1. 首先统计前 k 个字符中的元音数量作为初始值
  2. 从位置 k 开始滑动窗口，每次移动一位
  3. 移除窗口左边的字符（如果是元音则计数减1）
  4. 添加窗口右边的新字符（如果是元音则计数加1）
  5. 更新最大值

这种方法的优势是只需要遍历字符串一次，时间复杂度为 O(n)，相比暴力解法 O(n*k) 有显著提升。

为了快速判断字符是否为元音，可以使用集合或者直接字符比较。

代码实现

class Solution {
public:
    int maxVowels(string s, int k) {
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
        };
        
        int vowelCount = 0;
        // 计算前k个字符中的元音数量
        for (int i = 0; i < k; i++) {
            if (isVowel(s[i])) {
                vowelCount++;
            }
        }
        
        int maxVowels = vowelCount;
        
        // 滑动窗口
        for (int i = k; i < s.length(); i++) {
            // 移除左边的字符
            if (isVowel(s[i - k])) {
                vowelCount--;
            }
            // 添加右边的字符
            if (isVowel(s[i])) {
                vowelCount++;
            }
            maxVowels = max(maxVowels, vowelCount);
        }
        
        return maxVowels;
    }
};

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        
        # 计算前k个字符中的元音数量
        vowel_count = sum(1 for i in range(k) if s[i] in vowels)
        max_vowels = vowel_count
        
        # 滑动窗口
        for i in range(k, len(s)):
            # 移除左边的字符
            if s[i - k] in vowels:
                vowel_count -= 1
            # 添加右边的字符
            if s[i] in vowels:
                vowel_count += 1
            max_vowels = max(max_vowels, vowel_count)
        
        return max_vowels

public class Solution {
    public int MaxVowels(string s, int k) {
        var vowels = new HashSet<char> {'a', 'e', 'i', 'o', 'u'};
        
        int vowelCount = 0;
        // 计算前k个字符中的元音数量
        for (int i = 0; i < k; i++) {
            if (vowels.Contains(s[i])) {
                vowelCount++;
            }
        }
        
        int maxVowels = vowelCount;
        
        // 滑动窗口
        for (int i = k; i < s.Length; i++) {
            // 移除左边的字符
            if (vowels.Contains(s[i - k])) {
                vowelCount--;
            }
            // 添加右边的字符
            if (vowels.Contains(s[i])) {
                vowelCount++;
            }
            maxVowels = Math.Max(maxVowels, vowelCount);
        }
        
        return maxVowels;
    }
}

var maxVowels = function(s, k) {
    const vowels = new Set(['a', 'e', 'i', 'o', 'u']);
    
    let vowelCount = 0;
    // 计算前k个字符中的元音数量
    for (let i = 0; i < k; i++) {
        if (vowels.has(s[i])) {
            vowelCount++;
        }
    }
    
    let maxVowels = vowelCount;
    
    // 滑动窗口
    for (let i = k; i < s.length; i++) {
        // 移除左边的字符
        if (vowels.has(s[i - k])) {
            vowelCount--;
        }
        // 添加右边的字符
        if (vowels.has(s[i])) {
            vowelCount++;
        }
        maxVowels = Math.max(maxVowels, vowelCount);
    }
    
    return maxVowels;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是字符串长度。只需要遍历字符串一次
空间复杂度O(1)，只使用常数额外空间（元音集合大小固定）

相关题目