estoy haciendo leetcode 1456
Se me ocurrió una solución funcional, pero obtuve "Se excedió el límite de tiempo" para una de las pruebas . Usé el enfoque de ventana deslizante y creo que mi solución es O (n) (¿o estoy equivocado?).
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; }; Traté de ver si era porque el vowels.includes(s[right]) era de alguna manera un método realmente lento, pero según lo que leí, ese no es el caso, especialmente porque mi matriz solo tiene una longitud de 5.
¿Cómo puedo optimizar mi solución para que pase la prueba?
Terminé arreglando mi código con la ayuda de @Bergi.
El problema con mi respuesta original fue que seguí RESTABLECIENDO el puntero derecho a través de right = left - 1 en lugar de simplemente "deslizar la ventana" incrementando el puntero derecho. Mi solución original no funcionó a escala. Era O(n*k) y no O(n) como pensé originalmente.
Y debido a que seguí restableciendo el puntero derecho a right = left - 1 , en realidad estaba volviendo a verificar muchas veces el mismo carácter.
Mi nueva solución (que pasó) ahora se ve así:
/** * @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; };