Leetcode - how to optimize my solution using sliding window approach for maximum number of vowels in-CodePudding

I am doing leetcode 1456

I came up with a working solution but got "Time limit exceeded" for one of the tests. I used the sliding window approach and I believe my solution is O(n) (or am I wrong?).

var maxVowels = function(s, k) {
   let left = 0;
   let right = 0;
   let maxVowels = 0;
   let curVowels = 0;
   let vowels = ['a','e','i','o','u'];

   while (right < s.length) {
       let subStringLength = right - left   1;
       if (vowels.includes(s[right])) curVowels  ;
       
       if (subStringLength === k) {
           maxVowels = Math.max(maxVowels, curVowels);
           if (maxVowels === k) return maxVowels;
           curVowels = 0;
           left  ;
           right = left - 1;
       }           
       right  ;
   }
   return maxVowels;
};

I tried to see if it was because the vowels.includes(s[right]) method was somehow a really slow method but based on what I read that is not the case, especially since my array is only of length 5.

How can I optimize my solution such that it passes the test?

CodePudding user response：

Ended up fixing my code with the help @Bergi.

The problem with my original answer was that I kept RESETTING the right pointer via right = left - 1 rather than just "sliding the window" by incrementing the right pointer. My original solution did not work at scale. It was O(n*k) and not O(n) as I originally thought.

And because I kept resetting the right pointer to right = left - 1, I was actually doing a lot of re-checking of the same char.

My new solution (that passed) now looks like this:

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
 var maxVowels = function(s, k) {
    let left = 0;
    let right = 0;
    let maxVowels = 0;
    let curVowels = 0;
    let vowels = ['a','e','i','o','u'];
    
    while (right < s.length) {
        let subStringLength = right - left   1;
        if (vowels.includes(s[right])) curVowels  ;
        
        if (subStringLength === k) {
            maxVowels = Math.max(maxVowels, curVowels);
            if (vowels.includes(s[left])) curVowels--;
            left  ;
        }
        
        right  ;
        if (maxVowels === k) return maxVowels;
    }
    return maxVowels;
};