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?
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;
};