Subcadena más larga sin caracteres repetidos. ¿Cuál es la técnica óptima y su complejidad?
Opciones
- Fuerza bruta sobre todas las subcadenas, O(n³)
- Sliding window con un map de última posición vista, O(n) (Opción correcta)
- Ordenar primero los caracteres, O(n log n)
- Una tabla de DP sobre todos los pares de subcadenas, O(n²)
Respuesta
Sliding window con un map de última posición vista, O(n)
Por qué
Un sliding window es un rango [left, right] sobre el string que amplías y reduces en lugar de empezar de nuevo.
Avanza right un carácter cada vez. Si ese carácter ya aparece dentro de la ventana, mueve left justo después de su posición anterior. Lleva la cuenta de la mejor longitud de ventana.
Cada puntero solo avanza, así que el trabajo total es O(n).
Recuerda
Mejor subcadena o subarray contiguo → sliding window.