Dos punteros y ventana deslizante

Convierte recorridos anidados O(n²) en pasadas únicas O(n). Dos índices + mantener el estado de la ventana de forma incremental.

Tres formas

• Ventana variable: crece por la derecha, se encoge por la izquierda para conservar un invariante
• Dos extremos: converge desde ambos extremos de datos ORDENADOS
• Ventana fija: agrega-uno, quita-uno conforme se desliza (O(1)/paso)
• Truco común: actualiza al deslizar, no recalcules

Mira deslizarse la ventana

Substring más largo sin repeticiones de 'abcabcbb'. Verde = izquierda · naranja = derecha · azul = ventana. Entra una repetición (rojo) → la izquierda SALTA más allá. Respuesta: 'abc'.

Lineal vs cuadrático

Longitud 800: ventana 800 ops, fuerza bruta 320,000 → 400× menos. Tumba un factor entero de n.

Por qué es O(n) — y cuándo no lo es

• Cada puntero solo avanza → movimiento total ≤ 2n (amortizado, como KMP)
• Necesita una ventana MONÓTONA: extender viola, encoger por la izquierda restaura
• Se rompe con suma-de-subarray-con-negativos → usa un hash map de prefix-sums
• La variante de dos extremos necesita entrada ORDENADA

Para llevar

¿Ves un ciclo anidado que vuelve a recorrer rangos traslapados? Pregúntate: ¿puedo mantenerlo incrementalmente? La idea de "reutiliza lo que ya calculaste" del rolling hash / KMP, convertida en patrón. Lo que sigue: búsqueda binaria sobre la RESPUESTA, no sobre un array.