Problem

Given a string s and an integer k, return the maximum number of vowel letters in any substring ofs with lengthk.

Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.

Examples

Example 1

1
2
3

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2

1
2
3

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3

1
2
3

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
  • 1 <= k <= s.length

Solution

Method 1 – Sliding Window

Intuition

To find the maximum number of vowels in any substring of length k, we can use a sliding window of size k and count the vowels as the window moves. This allows us to efficiently update the count without re-scanning the whole substring each time.

Approach

  1. Define a set of vowels for quick lookup.
  2. Initialize a count of vowels in the first window of size k.
  3. Slide the window one character at a time:
    • Subtract the vowel count if the leftmost character is a vowel.
    • Add to the vowel count if the new rightmost character is a vowel.
    • Track the maximum count seen.
  4. Return the maximum count found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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, ans = 0, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (isVowel(s[i])) cnt++;
            if (i >= k && isVowel(s[i - k])) cnt--;
            ans = max(ans, cnt);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func maxVowels(s string, k int) int {
    isVowel := func(c byte) bool {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
    }
    cnt, ans := 0, 0
    for i := 0; i < len(s); i++ {
        if isVowel(s[i]) {
            cnt++
        }
        if i >= k && isVowel(s[i-k]) {
            cnt--
        }
        if cnt > ans {
            ans = cnt
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int maxVowels(String s, int k) {
        int cnt = 0, ans = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            if (isVowel(s.charAt(i))) cnt++;
            if (i >= k && 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';
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxVowels(s: String, k: Int): Int {
        fun isVowel(c: Char) = c in "aeiou"
        var cnt = 0
        var ans = 0
        for (i in s.indices) {
            if (isVowel(s[i])) cnt++
            if (i >= k && isVowel(s[i - k])) cnt--
            ans = maxOf(ans, cnt)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        vowels = set('aeiou')
        cnt = ans = 0
        for i, c in enumerate(s):
            if c in vowels:
                cnt += 1
            if i >= k and s[i - k] in vowels:
                cnt -= 1
            ans = max(ans, cnt)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn max_vowels(s: String, k: i32) -> i32 {
        let s = s.as_bytes();
        let mut cnt = 0;
        let mut ans = 0;
        for i in 0..s.len() {
            if b"aeiou".contains(&s[i]) {
                cnt += 1;
            }
            if i as i32 >= k && b"aeiou".contains(&s[i - k as usize]) {
                cnt -= 1;
            }
            ans = ans.max(cnt);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxVowels(s: string, k: number): number {
        const vowels = new Set(['a','e','i','o','u']);
        let cnt = 0, ans = 0;
        for (let i = 0; i < s.length; i++) {
            if (vowels.has(s[i])) cnt++;
            if (i >= k && vowels.has(s[i - k])) cnt--;
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the string once.
  • 🧺 Space complexity: O(1) — Only a few variables are used for counting.