[LeetCode] 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'.

Example:

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

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

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

Approach: We can take all the substring of size k of given string s and can check the number of vowels in those substrings and then we can return the maximum of all those counts but that will be time consuming task. 

We can use sliding window approach here to solve this problem. Obviously the size of the window here will be k. First we take the first k characters of s and count the number of vowels in it. Now we slide this k sized window one by one. The vowel count of the sliding window will be modified as follows:

curr_vowel_count =  curr_vowel_count - IsVowel(s[start]) + IsVowel(s[curr_index])

Here the curr_index is the end of the window and start is obviously the start of the window.

Implementation in C#:

        public int MaxVowels(string s, int k)

    {

        int length = s?.Length ?? 0;

        if (length < k)

        {

            return 0;

        }

        int currVowelCount = 0, i = 0;

        for (; i < k; ++i)

        {

            if (this.IsVowel(s[i]))

            {

                ++currVowelCount;

            }

        }

        int start = 0, maxVowelCount = currVowelCount;

        for (; i < length; ++i)

        {

            if (this.IsVowel(s[start++]))

            {

                --currVowelCount;

            }

            if (this.IsVowel(s[i]))

            {

                ++currVowelCount;

                maxVowelCount = maxVowelCount < currVowelCount ?

                                currVowelCount :

                                maxVowelCount;

            }

        }

        return maxVowelCount;

    }

    private bool IsVowel(char ch)

    {

        return ch == 'a' ||

               ch == 'e' ||

               ch == 'i' ||

               ch == 'o' ||

               ch == 'u';

    }

Complexity: O(n)