Sliding Window para substring sin repeticiones

Resolver el problema de Longest Substring Without Repeating Characters con Python te enseña a dominar la técnica de sliding window combinada con un hash map. Es un ejercicio clave si te preparas para entrevistas técnicas y quieres entender cómo optimizar búsquedas en cadenas a complejidad lineal.

¿Cómo se inicializan los apuntadores en sliding window?

La solución arranca declarando un apuntador inicio en cero, que marca dónde empieza el substring válido [0:31]. El segundo apuntador, el fin, no se declara como variable suelta: se integra directamente en el for que recorre el string usando enumerate, porque su único trabajo es avanzar de uno en uno.

Esta decisión hace el código más limpio. El inicio sí necesita vivir afuera porque cambia de forma condicional, mientras que fin siempre suma uno en cada iteración.

¿Qué es un sliding window en algoritmos? Es una técnica donde dos apuntadores delimitan un rango dentro de una secuencia. Ese rango se expande o contrae según las condiciones del problema, evitando recorrer la estructura múltiples veces.

¿Para qué sirve el hash map de caracteres a posición?

Se crea un diccionario llamado caracteres_a_posicion que guarda la última posición vista de cada carácter [1:30]. Si el string es a, b, c, a, cuando el recorrido llegue al índice 3, la entrada de la a se actualiza de 0 a 3.

Este mapa permite saltar el inicio directamente a la posición siguiente del duplicado, sin perder los caracteres intermedios que sí formaban un substring válido. Si solo se rompió por una letra, no tiene sentido reiniciar desde cero.

También se declara la variable mayor_longitud en cero, que va guardando el récord del substring más largo encontrado hasta el momento.

¿Cómo se mueve el apuntador inicio cuando hay un duplicado?

Dentro del ciclo se revisa el carácter actual en fin. Si ese carácter ya existe como llave en el mapa, hay un duplicado potencial y el inicio debe saltar a la posición guardada más uno.

Pero hay una trampa importante. El mapa nunca se vacía, así que puede contener llaves de substrings antiguos que ya quedaron fuera de la ventana actual. Por eso la condición real es:

• El carácter está en el mapa.
• Y la posición guardada es mayor o igual que el inicio actual.

Si la posición del duplicado es anterior al inicio, se trata de basura de un substring viejo y se ignora. Esto evita retroceder el inicio por error.

¿Cómo se actualiza la longitud máxima en cada iteración?

Después de manejar el duplicado, se actualiza el mapa con la posición actual del carácter. Luego se calcula la longitud del substring vigente con la fórmula fin - inicio + 1, que cuenta los elementos entre los dos apuntadores incluyendo el actual [5:30].

Se compara con mayor_longitud usando max() y se conserva el valor más alto. Al terminar el for, se retorna mayor_longitud.

¿Cuál es la complejidad temporal y espacial del algoritmo?

Probando con el string a, b, c, d, a, e, f con un carácter extra, el algoritmo retorna 6, que corresponde al substring más largo sin repeticiones. La traza paso a paso confirma que la lógica funciona desde la primera iteración.

¿Cuál es la complejidad de Longest Substring Without Repeating Characters? Temporal es O(n), porque recorres el string una sola vez. Espacial es O(n) si asumes alfabeto ilimitado, o O(1) si trabajas con un alfabeto fijo como las 26 letras del inglés.

La diferencia espacial depende de cómo definas el problema. Si el enunciado limita el alfabeto a un valor constante, el mapa nunca crece más allá de ese tamaño y se considera espacio constante. Si aceptas cualquier carácter Unicode, el mapa puede crecer proporcional al input.

¿Qué habilidades practicas con este ejercicio?

• Manejo de la técnica sliding window con dos apuntadores [0:31].
• Uso de hash maps para registrar posiciones y evitar recorridos extra [1:30].
• Análisis de casos borde, como duplicados fuera de la ventana activa [3:50].
• Cálculo de longitud entre apuntadores con fin - inicio + 1 [5:30].
• Análisis de complejidad temporal y espacial según el alfabeto de entrada [7:40].

Si te animas, comparte en los comentarios qué lenguaje elegiste tú para implementarlo y cómo manejaste la condición del duplicado fuera de la ventana.