1456. Maximum Number of Vowels in a Substring of Given Length

• Why you may want to read this note
• Problem
• Sliding window solution O(n) & O(1)

Why you may want to read this note

As a Software Engineer at Microsoft I didn’t do LeetCode interview questions for a long time already. Now I’m refreshing my skills in algorithm questions and these set of articles are for myself in future and for whoever is solving it right now.

We are going to discuss the thinking process, insights, worse/better approaches, complexity analysis

This is our list: https://leetcode.com/studyplan/leetcode-75/

The problem: 1456. Maximum Number of Vowels in a Substring of Given Length

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’, and ‘u’.

Sliding window solution O(n) & O(1)

We are iterating over the string once, and increasing the counter every time we see a vowel. When we reach window (i - k … k) we should maintain the size of the window, so each time we are moving window 1 character forward, we remove 1 character from the behind.

var maxVowels = function(s, k) {
    let set = new Set(['a', 'e', 'i', 'o', 'u'])
    let count = 0;
    let max = 0;

    for (let i = 0; i < s.length; i++) {
        if (set.has(s[i])) {
            count++
        }
        max = Math.max(max, count)

        let leftInd = (i + 1) - k
        if (leftInd >= 0 && set.has(s[leftInd])) {
            count--
        }
    }

    return max
};

Runtime Complexity: O(n) we are traversing the array only once. set.has() is O(1) since it is a hashset.

Space Complexity: O(1) as we are using 2 variables and set with a constant number of characters (5).