LeetCode: Max count of vowel is a given string in a given interval.

MaxVowel.java

class Solution {
    public int maxVowels(String s, int k) {
        int slen = s.length();
        int[] dp = new int[slen];
        int vcc = 0;
        for (int i = 0; i < slen; i++){
            if (isVowel(s.charAt(i))){
                dp[i] = ++vcc;
            } else {
                dp[i] = vcc;
            }
        }
        int ret = 0;
        for (int i = 0; i < (slen-k+1); i++){
            int end = i+k-1;
            if (i == 0){
                ret = Math.max(ret, dp[end]);
            } else {
                ret = Math.max(ret, (dp[end] - dp[i-1]));
            }
        }
        return ret;
    }

    private boolean isVowel(Character c){
        return (
            c == 'a' ||
            c == 'e' ||
            c == 'i' ||
            c == 'o' ||
            c == 'u'
        );
    }
}

Question

Given with a string and an int value k. Find the max number of vowels in the interval k in the given string.

Solution

The above problem has been solved using two approaches as given below

• Sliding Window
• Dynamic Programming

Sliding Window

• Count the total number of vowels in the k interval.
• Now iterate from k to the last index while performing
  • if the (i-k) value is a vowel then decrease the count by 1
  • if the (i) value is a vowel then increase the count by 1
  • if the count is greater than the current max vowels count then replace.
• return the max vowels count.

The above approach beats 77 % of the total submissions with a runtime of 15 ms. (Done by me.)

class Solution {
    public int maxVowels(String s, int k) {
        int sum = 0;
        int slen = s.length();
        for (int i = 0; i < k; i++){
            if (isVowel(s.charAt(i))){
                sum++;
            }
        }
        int windowSum = sum;
        for (int i = k; i < slen; i++){
            if (isVowel(s.charAt(i - k))){
                windowSum--;
            }
            if (isVowel(s.charAt(i))){
                windowSum++;
            }
            sum = Math.max(sum, windowSum);
        }
        return sum;
    }

    private boolean isVowel(Character c){
        return (
            c == 'a' ||
            c == 'e' ||
            c == 'i' ||
            c == 'o' ||
            c == 'u'
        );
    }
}

Dynamic Programming

• Iterate through the whole string length while updating the integer array of the same length as the string as given below
  • if the current value is a vowel then increment the current vowel count and assign it to the same index in the integer array.
  • if the current value is not a vowel then assign the current vowel count as it is to the same index in the integer array.
• Now iterate from 0 to (string.length() +k-1) index.
  • if the current index is 0
    • then, max = Math.max(max, intArr[end]) where end = (i - k + 1)
    • else, max = Math.max(max, (intArr[end] - intArr[i-1]))
• return max

The above approach beats 97 % of the total solutions submitted with a runtime of 9 ms.