Let's Code_: LeetCode Medium: Maximum Number of Vowels in a Substring of Given Length

Tuesday, September 22, 2020

LeetCode Medium: Maximum Number of Vowels in a Substring of Given Length

Hello All,

Today’s coding problem is a Medium level LeetCode problem. Problem #1456: Maximum Number of Vowels in a Substring of Given Length

Link to Problem: https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/

Problem Approach: Sliding Window

Time Complexity: O(n) where n is the number of characters in the input string.

Space Complexity: O(1) extra space

Accepted Java solution using Sliding Window:

class Solution {
    public int maxVowels(String s, int k) {
        if (s==null || s.length()<k) {
            return 0;
        }
        
        int maxVowelCnt = 0;
        int currentVowelCnt = 0;
        for (int i=0; i<=s.length()-k; i++) {
            if (i==0) { //1st window only
                for (int j=i; j<i+k; j++) {
                    if (isVowel(s.charAt(j)))
                        currentVowelCnt++;
                }
            } else { //remaining windows
                if(isVowel(s.charAt(i+k-1)))
                    currentVowelCnt++;
                if(isVowel(s.charAt(i-1)))
                    currentVowelCnt--;
            }
            
            maxVowelCnt = Math.max(maxVowelCnt, currentVowelCnt);
        }
        
        return maxVowelCnt;
    }
    
    private boolean isVowel(char c) {
        return c=='a' || c=='e' || c=='i' || c=='o' || c=='u' ;
    }
}