Subcadena más larga sin repetir caracteres

El problema Longest Substring Without Repeating Characters es uno de los retos clásicos para entrenar el patrón de ventana deslizante (sliding window) en estructuras de datos. Aprenderás a identificar la subcadena más larga sin caracteres repetidos dentro de una cadena, optimizando la solución a una complejidad temporal O(n). Es ideal si te preparas para entrevistas técnicas o quieres dominar algoritmos eficientes sobre cadenas.

¿Qué pide el problema Longest Substring Without Repeating Characters?

El enunciado es directo: dada una cadena S, debes devolver la longitud de la subcadena más larga que no contenga caracteres repetidos. Lo que se retorna no es la subcadena en sí, sino su tamaño numérico.

Mira este caso: si la entrada es abcabcb, la respuesta es 3. ¿Por qué? Porque las subcadenas válidas sin repetir son abc, bca, cab, abc o bcb, y todas tienen longitud tres. Ninguna alcanza una longitud mayor.

¿Qué es una subcadena sin repetir caracteres? Es un fragmento contiguo de la cadena original donde cada carácter aparece una sola vez. En cuanto se repite uno, esa subcadena termina.

¿Cómo aplicar el patrón ventana deslizante a este reto?

El patrón sliding window o ventana deslizante consiste en mantener un rango dentro de la cadena que se expande o contrae según una condición. Aquí, la condición es que no haya caracteres repetidos dentro de la ventana.

La idea general que puedes diseñar:

• Define dos punteros que representen el inicio y el final de la ventana.
• Avanza el puntero derecho añadiendo caracteres a la ventana.
• Cuando aparezca un carácter repetido, mueve el puntero izquierdo hasta eliminar la repetición.
• Lleva un registro de la longitud máxima alcanzada en cada paso.

Este enfoque evita revisar todas las subcadenas posibles, que sería una solución cuadrática.

¿Por qué la complejidad debe ser O(n)? Porque cada carácter de la cadena se visita como máximo dos veces: una al expandir la ventana y otra al contraerla. Eso mantiene el tiempo lineal frente al tamaño de la entrada.

¿Cómo interpretar los ejemplos de entrada y salida?

Veamos cómo se traduce la lógica en los casos propuestos en clase [00:25]:

1. Entrada abcabcb → salida 3. Tienes abc, luego se repite la a y la ventana se reinicia. Todas las subcadenas válidas tienen tamaño tres.
2. Una entrada más larga sigue la misma lógica: el algoritmo recorre, expande y contrae la ventana, devolviendo siempre la longitud máxima encontrada.

Lo importante es notar que el resultado es un número, no la cadena. Eso simplifica el diseño porque solo necesitas comparar tamaños.

¿Qué conceptos clave debes dominar para resolverlo?

Antes de implementar, asegúrate de tener claros estos elementos que aparecen en el reto:

• Subcadena: fragmento contiguo de una cadena, distinto de una subsequence que puede ser no contigua.
• Ventana deslizante: técnica con dos punteros que avanzan sobre la estructura para mantener un rango válido [00:50].
• Complejidad temporal O(n): el tiempo de ejecución crece de forma lineal con el tamaño de la entrada.
• Estructura auxiliar: típicamente un set o hash map para verificar en tiempo constante si un carácter ya está en la ventana.

Con estos conceptos en la cabeza, el diseño fluye casi solo.

¿Cuál es el reto antes de la siguiente clase?

No implementes todavía. Primero diseña la solución en papel o en pseudocódigo y asegúrate de que cumpla con la complejidad O(n) [01:15]. Piensa qué estructura usarás para detectar repeticiones y cómo moverás los punteros cuando aparezca un carácter ya visto.

Cuéntame en los comentarios cómo abordaste el diseño, qué dudas te surgieron y qué estructura elegiste para la ventana. Nos leemos ahí.