Subcadena más larga sin repeticiones
Siga las últimas posiciones vistas en una ventana
Subcadena más larga sin repeticiones es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Un problema clásico de ventanas
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. 🔤
La trampa de la fuerza bruta
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.
Ventana de caracteres únicos
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.
Recuerde las últimas posiciones
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.
last = {}
left = 0
best = 0Recorra cada carácter
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.
for right, ch in enumerate(s):Salte el puntero izquierdo
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.
if ch in last and last[ch] >= left:
left = last[ch] + 1Actualice y mida
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.
last[ch] = right
best = max(best, right - left + 1)Por qué es importante la comprobación
La comprobación last[ch] >= left es esencial. Sin ella, una posición antigua fuera de la ventana haría retroceder incorrectamente a left.
Tiempo y espacio lineales
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.
Casos límite que debe cubrir
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 patrón reutilizable
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.
Comprobación rápida
Mantiene el último índice de cada carácter mientras busca la subcadena única más larga.
Resumen
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). ✅
Preguntas frecuentes
¿La lección «Subcadena más larga sin repeticiones» es gratis?
Sí — el texto completo de «Subcadena más larga sin repeticiones» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Subcadena más larga sin repeticiones»?
Siga las últimas posiciones vistas en una ventana Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Subcadena más larga sin repeticiones»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Sumas de ventanas de tamaño fijo
- Ventana variable con dos punteros
- Subcadena más larga sin repeticiones
- Cuente ventanas que cumplen una regla