Maximum Number of Vowels in a Substring of Given Length

medium string sliding window

Problem

Given a string s and an integer k. Return the maximum number of vowel letters in any substring of s with length k. Vowel letters in English are (a, e, i, o, u).

Inputs = "leetcode", k = 3

Output2

Window "lee" contains 2 vowels (e, e), the maximum over all length-3 substrings.

def max_vowels(s, k):
    V = set("aeiou")
    count = sum(1 for c in s[:k] if c in V)
    best = count
    for i in range(k, len(s)):
        if s[i] in V: count += 1
        if s[i - k] in V: count -= 1
        if count > best: best = count
    return best

function maxVowels(s, k) {
  const isV = c => "aeiou".includes(c);
  let count = 0;
  for (let i = 0; i < k; i++) if (isV(s[i])) count++;
  let best = count;
  for (let i = k; i < s.length; i++) {
    if (isV(s[i])) count++;
    if (isV(s[i - k])) count--;
    if (count > best) best = count;
  }
  return best;
}

class Solution {
    public int maxVowels(String s, int k) {
        String V = "aeiou";
        int count = 0;
        for (int i = 0; i < k; i++) if (V.indexOf(s.charAt(i)) != -1) count++;
        int best = count;
        for (int i = k; i < s.length(); i++) {
            if (V.indexOf(s.charAt(i)) != -1) count++;
            if (V.indexOf(s.charAt(i - k)) != -1) count--;
            if (count > best) best = count;
        }
        return best;
    }
}

int maxVowels(string s, int k) {
    string V = "aeiou";
    int count = 0;
    for (int i = 0; i < k; i++) if (V.find(s[i]) != string::npos) count++;
    int best = count;
    for (int i = k; i < (int)s.size(); i++) {
        if (V.find(s[i]) != string::npos) count++;
        if (V.find(s[i - k]) != string::npos) count--;
        if (count > best) best = count;
    }
    return best;
}

Explanation

Every substring we consider has the same fixed length k, so instead of recounting vowels for each one, we keep a rolling count of vowels in the current window.

First we count the vowels in the opening window of the first k characters. Then we slide one position at a time: if the character entering on the right is a vowel we add 1, and if the character leaving on the left was a vowel we subtract 1.

After each slide we compare the running count against best and keep the maximum. The vowel set is just a, e, i, o, u.

Example: s = "leetcode", k = 3. The first window "lee" has 2 vowels. Sliding to "eet" keeps 2, then counts drop as consonants enter. The maximum stays 2, the answer.

Each slide is a couple of cheap checks, so the whole pass is linear time with constant extra space.

Time: O(n) Space: O(1)