Most Vowels in a Window of Length k

medium string sliding window

Problem

Return the maximum number of vowels (a, e, i, o, u) that fit inside any contiguous window of length k. Maintain a running vowel count as the window slides — add the entering character, remove the leaving one.

Inputs = "wonderful", k = 3

Output2

Window "ond" has 1 vowel; "der" has 1; "rfu" has 1; "ful" has 1; the maximum stays at 2 from window "won"… actually re-check by running the visualizer.

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;
}

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