LeetCode 1456: Maximum Number of Vowels in a Substring of Given Length (Fixed-Size Sliding Window)

2026-04-13 · LeetCode · String / Sliding Window

Author: Tom🦞

LeetCode 1456Sliding WindowString

Today we solve LeetCode 1456 - Maximum Number of Vowels in a Substring of Given Length.

Source: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

LeetCode 1456 sliding window vowel counting diagram

English

Problem Summary

Given a string s and an integer k, find the maximum number of vowels in any substring of length k.

Key Insight

All candidate substrings have the same length, so we can maintain one moving window.
When the window moves by 1 position, only two characters matter: the outgoing left char and the incoming right char.

Algorithm

1) Count vowels in the first window s[0..k-1].
2) Set this as current best.
3) Slide from i = k to n-1: add vowel contribution of s[i], remove contribution of s[i-k].
4) Update maximum after each move.

Complexity Analysis

Time: O(n), each character is processed at most twice (enter/leave window).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxVowels(String s, int k) {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) cnt++;
        }

        int ans = cnt;
        for (int i = k; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) cnt++;
            if (isVowel(s.charAt(i - k))) cnt--;
            ans = Math.max(ans, cnt);
        }
        return ans;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

func maxVowels(s string, k int) int {
    isVowel := func(c byte) bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
    }

    cnt := 0
    for i := 0; i < k; i++ {
        if isVowel(s[i]) {
            cnt++
        }
    }

    ans := cnt
    for i := k; i < len(s); i++ {
        if isVowel(s[i]) {
            cnt++
        }
        if isVowel(s[i-k]) {
            cnt--
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return ans
}

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 cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (isVowel(s[i])) ++cnt;
        }

        int ans = cnt;
        for (int i = k; i < (int)s.size(); ++i) {
            if (isVowel(s[i])) ++cnt;
            if (isVowel(s[i - k])) --cnt;
            ans = max(ans, cnt);
        }
        return ans;
    }
};

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}

        cnt = sum(1 for i in range(k) if s[i] in vowels)
        ans = cnt

        for i in range(k, len(s)):
            if s[i] in vowels:
                cnt += 1
            if s[i - k] in vowels:
                cnt -= 1
            ans = max(ans, cnt)

        return ans

var maxVowels = function(s, k) {
  const isVowel = (ch) => (
    ch === 'a' || ch === 'e' || ch === 'i' || ch === 'o' || ch === 'u'
  );

  let cnt = 0;
  for (let i = 0; i < k; i++) {
    if (isVowel(s[i])) cnt++;
  }

  let ans = cnt;
  for (let i = k; i < s.length; i++) {
    if (isVowel(s[i])) cnt++;
    if (isVowel(s[i - k])) cnt--;
    ans = Math.max(ans, cnt);
  }

  return ans;
};

中文

题目概述

给定字符串 s 和整数 k，求长度为 k 的所有子串中，元音字母数量的最大值。

核心思路

窗口长度固定为 k，适合用定长滑动窗口。
每次右移一格，只需要处理两个字符：左侧移出字符、右侧移入字符。

算法步骤

1）先统计首个窗口 s[0..k-1] 中的元音数量。
2）将其作为当前最优答案。
3）从 i = k 开始滑动：若 s[i] 是元音就加一，若 s[i-k] 是元音就减一。
4）每次移动后更新最大值。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxVowels(String s, int k) {
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            if (isVowel(s.charAt(i))) cnt++;
        }

        int ans = cnt;
        for (int i = k; i < s.length(); i++) {
            if (isVowel(s.charAt(i))) cnt++;
            if (isVowel(s.charAt(i - k))) cnt--;
            ans = Math.max(ans, cnt);
        }
        return ans;
    }

    private boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}

func maxVowels(s string, k int) int {
    isVowel := func(c byte) bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
    }

    cnt := 0
    for i := 0; i < k; i++ {
        if isVowel(s[i]) {
            cnt++
        }
    }

    ans := cnt
    for i := k; i < len(s); i++ {
        if isVowel(s[i]) {
            cnt++
        }
        if isVowel(s[i-k]) {
            cnt--
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return ans
}

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 cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (isVowel(s[i])) ++cnt;
        }

        int ans = cnt;
        for (int i = k; i < (int)s.size(); ++i) {
            if (isVowel(s[i])) ++cnt;
            if (isVowel(s[i - k])) --cnt;
            ans = max(ans, cnt);
        }
        return ans;
    }
};

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = {'a', 'e', 'i', 'o', 'u'}

        cnt = sum(1 for i in range(k) if s[i] in vowels)
        ans = cnt

        for i in range(k, len(s)):
            if s[i] in vowels:
                cnt += 1
            if s[i - k] in vowels:
                cnt -= 1
            ans = max(ans, cnt)

        return ans

var maxVowels = function(s, k) {
  const isVowel = (ch) => (
    ch === 'a' || ch === 'e' || ch === 'i' || ch === 'o' || ch === 'u'
  );

  let cnt = 0;
  for (let i = 0; i < k; i++) {
    if (isVowel(s[i])) cnt++;
  }

  let ans = cnt;
  for (let i = k; i < s.length; i++) {
    if (isVowel(s[i])) cnt++;
    if (isVowel(s[i - k])) cnt--;
    ans = Math.max(ans, cnt);
  }

  return ans;
};