Acompanhe um intervalo com uma janela deslizante

Muitos problemas perguntam sobre um subarray ou substring contíguo: a maior substring sem repetições, o menor subarray com soma de pelo menos k, a soma máxima de k itens consecutivos. Testar todos os intervalos é O(n²) ou pior. Uma janela deslizante mantém um intervalo [left, right] e atualiza o estado dele aos poucos conforme as bordas se movem, para que cada elemento entre e saia da janela no máximo uma vez.

• Tamanho fixo: a janela sempre tem k itens. Some o novo elemento da direita e subtraia o elemento que sai pela esquerda.
• Tamanho variável: expanda right um passo de cada vez; enquanto a janela quebrar uma regra, encolha-a pela left. Registre a melhor janela válida no caminho.

O estado da janela - uma soma acumulada, ou um dicionário com contagens de caracteres ou com as últimas posições vistas - é o que torna cada passo O(1).

Para “maior substring sem caracteres repetidos”, mantenha um dicionário com o último índice de cada caractere. Quando o caractere novo já foi visto dentro da janela atual, pule left para depois da posição anterior dele. A resposta é o maior right - left + 1 visto. Como left só avança, a varredura inteira é O(n).