Subcadena más larga sin repeticiones

Encuentre la subcadena más larga sin caracteres repetidos. Es un clásico de las ventanas deslizantes que aparece en casi todos los jueces en línea. 🔤

Comprobar si hay duplicados en cada subcadena cuesta aproximadamente O(n^2) o más. Para cadenas largas es demasiado lento, así que se necesita un recorrido más inteligente.

Mantenga una ventana que siempre contenga caracteres distintos. Expándala por la derecha y, cuando aparezca una repetición, redúzcala desde la izquierda hasta eliminarla.

Guarde el último índice de cada carácter en un diccionario. Así sabrá al instante dónde se vio por última vez una repetición durante el recorrido.

Recorra la cadena con right, leyendo tanto el índice como el carácter en cada paso. Esto hace avanzar la ventana una posición a la vez.

Si el carácter se vio dentro de la ventana actual, mueva left justo después de su última posición. Así elimina el duplicado de un solo movimiento.

Registre la nueva posición de este carácter; entonces la ventana de left a right no tendrá duplicados. Su longitud es right menos left más uno.

La comprobación last[ch] >= left es esencial. Sin ella, una posición antigua fuera de la ventana haría retroceder incorrectamente a left.

Cada carácter se visita una vez y left solo avanza hacia delante, por lo que el recorrido cuesta O(n). El diccionario utiliza espacio para los caracteres distintos.

Una cadena vacía da como resultado cero, y una cadena formada por una sola letra repetida da como resultado uno. Verifique ambos casos antes de enviar la solución para evitar un WA traicionero.

El mapa de última aparición junto con un puntero izquierdo que salta se generaliza a muchos problemas de unicidad, como las ventanas con como máximo una repetición.

Mantiene el último índice de cada carácter mientras busca la subcadena única más larga.

Deslice una ventana de caracteres únicos, guarde la última posición de cada uno y salte left después de las repeticiones. Esto resuelve el problema clásico en O(n). ✅