La subcadena más larga sin caracteres repetidos — Sliding Window
En mi artículo anterior trabajé con Binary Search, utilizando un algoritmo conocido para resolver un problema concreto.
Jose Gratereaux
Author
Para este segundo Code Kata quiero hacer algo diferente: no empezar pensando en el algoritmo, sino en el problema y en cómo podemos llegar gradualmente a una solución eficiente.
En esta ocasión vamos a resolver un problema clásico de entrevistas técnicas:
Dada una cadena de caracteres, encuentra la longitud de la subcadena más larga que no contenga caracteres repetidos.
Por ejemplo:
Input: "abcabcbb"
Output: 3
La respuesta es 3 porque "abc" es la subcadena más larga sin caracteres repetidos.
El problema
Tenemos una cadena:
"abcabcbb"
Queremos encontrar la longitud de la subcadena más larga cuyos caracteres sean todos diferentes.
Algunos ejemplos:
"abcabcbb" → 3
"bbbbb" → 1
"pwwkew" → 3
"" → 0
En "abcabcbb", tenemos:
abc
que tiene tres caracteres diferentes.
Pero "abca" no es válida porque a aparece dos veces.
La pregunta entonces es:
¿Cómo podemos recorrer la cadena sin tener que comprobar todas las posibles subcadenas?
Mi primera aproximación
Una primera idea bastante natural sería generar todas las subcadenas posibles y comprobar cuáles no contienen caracteres repetidos.
Por ejemplo, para:
"abc"
podríamos analizar:
"a" "ab" "abc" "b" "bc" "c"
Esto funciona.
El problema es que el número de combinaciones crece rápidamente a medida que aumenta el tamaño de la cadena.
En el peor caso, terminaríamos haciendo mucho trabajo repetido.
Y aquí aparece una pregunta importante:
¿Podemos reutilizar información que ya hemos obtenido mientras recorremos la cadena?
La respuesta es sí.
La idea de Sliding Window
En lugar de pensar en cada subcadena individualmente, podemos mantener una ventana que represente la parte de la cadena que estamos analizando actualmente.
Imaginemos:
abcabcbb
^^^
Nuestra ventana inicialmente contiene:
"abc"
Todos sus caracteres son diferentes.
Ahora avanzamos:
abcabcbb
^^^
El siguiente carácter es b.
Pero b ya existe dentro de nuestra ventana.
En lugar de empezar todo de nuevo, podemos mover el inicio de la ventana hasta eliminar el carácter repetido.
La ventana pasa a ser:
"bca"
Y podemos continuar.
Esta es la idea fundamental de Sliding Window:
Mantener un rango válido y mover sus límites solamente cuando sea necesario.
Una estructura para recordar los caracteres
Necesitamos saber rápidamente si un carácter ya apareció dentro de nuestra ventana.
Podríamos utilizar un Set.
Un Set nos permite almacenar valores únicos y comprobar rápidamente si un valor ya existe.
Por ejemplo:
const characters = new Set();
characters.add("a");
characters.add("b");
characters.has("a"); // true
characters.has("c"); // false
Esto encaja perfectamente con nuestro problema.
La solución
Esta es la implementación completa:
function lengthOfLongestSubstring(s) {
const characters = new Set();
let left = 0;
let maxLength = 0;
for (let right = 0; right < s.length; right++) {
while (characters.has(s[right])) {
characters.delete(s[left]);
left++;
}
characters.add(s[right]);
maxLength = Math.max(
maxLength,
right - left + 1
);
}
return maxLength;
}
Ahora vamos a analizarla paso a paso.
Paso 1: Crear nuestro Set
const characters = new Set();
Este Set representa los caracteres que actualmente forman parte de nuestra ventana.
Si nuestra ventana es:
"abc"
entonces:
characters = { a, b, c }
La ventaja es que podemos preguntar rápidamente:
characters.has(character)
para saber si un carácter ya está dentro de la ventana.
Paso 2: Definir el límite izquierdo
let left = 0;
left representa el comienzo de nuestra ventana.
Al principio estamos en:
abcabcbb
^
Por lo tanto:
left = 0
Paso 3: Guardar la longitud máxima
let maxLength = 0;
Necesitamos recordar cuál ha sido la ventana válida más grande que hemos encontrado.
Inicialmente no hemos procesado ningún carácter:
maxLength = 0
Paso 4: Mover el límite derecho
for (let right = 0; right < s.length; right++) {
Aquí right representa el final de nuestra ventana.
Mientras avanzamos por la cadena:
abcabcbb
^
luego:
abcabcbb
^
y después:
abcabcbb
^
La ventana crece hacia la derecha.
Paso 5: ¿Tenemos un carácter repetido?
Esta es probablemente la parte más importante del algoritmo:
while (characters.has(s[right])) {
Estamos preguntando:
¿El carácter que acabamos de encontrar ya está dentro de nuestra ventana?
Si no está, podemos simplemente incorporarlo.
Pero si ya existe, nuestra ventana dejó de ser válida.
Por ejemplo:
abcab
^^^
Tenemos:
{a, b, c}
y encontramos otro b.
Ahora tenemos un problema:
abcb
b aparece dos veces.
Tenemos que reducir la ventana desde la izquierda.
Paso 6: Mover el límite izquierdo
characters.delete(s[left]);
left++;
Primero eliminamos de nuestro Set el carácter que está en la posición left.
Después movemos left una posición hacia la derecha.
Por ejemplo:
abcab
^ ^
Si left apunta a a, eliminamos a:
characters.delete("a");
y avanzamos:
left++;
Ahora nuestra ventana comienza en el siguiente carácter.
El while continúa haciendo esto hasta que el carácter repetido deje de estar dentro de la ventana.
Esto es importante.
No movemos left una sola vez.
Lo movemos hasta recuperar una ventana válida.
Paso 7: Añadir el nuevo carácter
Una vez que sabemos que el carácter no está repetido:
characters.add(s[right]);
Ahora podemos incorporarlo a nuestra ventana.
Paso 8: Calcular el tamaño de la ventana
Tenemos:
right - left + 1
¿Por qué + 1?
Porque tanto left como right son posiciones incluidas en la ventana.
Por ejemplo:
0 1 2
a b c
Si:
left = 0
right = 2
tenemos:
2 - 0 + 1 = 3
Por lo tanto, la ventana contiene tres caracteres.
Paso 9: Guardar el máximo
Finalmente:
maxLength = Math.max(
maxLength,
right - left + 1
);
Comparamos el tamaño de la ventana actual con nuestro máximo anterior.
Si la ventana actual es más grande, actualizamos maxLength.
Viendo el algoritmo en acción
Tomemos:
"abcabcbb"
Comenzamos con:
left = 0
y movemos right.
right = 0
Encontramos:
a
Ventana:
"a"
Longitud:
1
Máximo:
1
right = 1
Encontramos:
b
Ventana:
"ab"
Longitud:
2
Máximo:
2
right = 2
Encontramos:
c
Ventana:
"abc"
Longitud:
3
Máximo:
3
right = 3
Encontramos otro:
a
Pero a ya existe.
Tenemos que mover left.
Eliminamos el primer a y avanzamos left.
Nuestra nueva ventana termina siendo:
"bca"
Seguimos teniendo una ventana válida de longitud 3.
El proceso continúa de la misma manera hasta terminar la cadena.
El resultado final es:
3
¿Por qué esta solución es eficiente?
Una solución ingenua podría terminar analizando muchas subcadenas diferentes.
Nuestra solución utiliza dos índices:
left right
right solamente avanza.
left también solamente avanza.
Ninguno de los dos vuelve hacia atrás.
Por eso, aunque tenemos un while dentro del for, no significa que tengamos automáticamente una complejidad O(n²).
Cada carácter puede entrar y salir del Set como máximo una vez por cada movimiento de las ventanas.
Por lo tanto:
Time Complexity: O(n)
Y necesitamos almacenar los caracteres de la ventana:
Space Complexity: O(n)
Lo importante no es memorizar Sliding Window
Podría simplemente decir:
"Para este problema usamos Sliding Window."
Pero eso no explica realmente cómo llegamos a la solución.
Lo interesante es observar el razonamiento:
Necesitamos encontrar una subcadena.
Una subcadena representa un rango continuo.
Queremos mantener ese rango válido.
Cuando aparece un carácter repetido, no necesitamos empezar desde cero.
Podemos mover el inicio de nuestro rango.
Necesitamos una estructura que nos permita saber rápidamente qué caracteres tenemos.
Set resuelve esa necesidad.
El resultado es una ventana que avanza por la cadena.
Ese patrón de pensamiento es mucho más útil que memorizar una implementación.
Conclusión
Este problema parece sencillo al principio, pero contiene una idea bastante poderosa.
La clave no está solamente en recorrer la cadena, sino en evitar repetir trabajo que ya hicimos.
Sliding Window es especialmente útil cuando trabajamos con datos secuenciales y necesitamos analizar rangos continuos: strings, arrays, streams de datos, métricas, logs y muchos otros escenarios.
Y quizás esa sea la lección más importante de este Code Kata:
Una buena solución no siempre consiste en hacer el trabajo más rápido. A veces consiste en no hacer el mismo trabajo dos veces.
En el próximo problema, podemos tomar otro patrón algorítmico y repetir el mismo proceso: comenzar con el problema, explorar una solución inicial y descubrir paso a paso una solución más eficiente.