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

思路

滑动窗口

代码

var maxVowels = function(s, k) {
  // 元音字母集
  let keys = new Set(['a', 'e', 'i', 'o', 'u'])
  let count = 0;
  let left = 0, right = 0, winLen = 0;
  while(right <= s.length) {
    let cur = s[right]
    // 窗口扩大
    if (keys.has(cur)) {
      winLen ++;
    }
    // 窗口缩小
    if (right - left >= k) {
      if (keys.has(s[left])) {
        winLen --;
      }
      left ++;
    }
    count = Math.max(count, winLen);
    // 找到最多k个，直接退出
    if (count == k) break;

    right ++;
  }
  return count;
};

复杂度

• 时间复杂度 $O(N)$
• 空间复杂度 $O(1)$