Padrão 2: Sliding Window com frequência

O sliding window que você aprendeu no Array volta aqui — só que o estado da janela deixa de ser um número e passa a ser um mapa de contagens. Com isso, ele resolve a maior família de problemas de string do LeetCode.

🎯

Tente primeiro: Longest Substring Without Repeating Characters

Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.

Dada uma string s, retorne o comprimento da maior substring (contígua) sem caracteres repetidos.

Exemplo: s = "abcabcbb" → 3 (a substring "abc"). s = "bbbbb" → 1.

Carregando editor…

Tentou? Gerar todas as substrings e checar repetição em cada uma é O(n²) ou O(n³). O incômodo: ao mover o começo, você recomeça a verificação do zero. A teoria abaixo traz o sliding window de volta — agora com um estado mais rico.

A teoria: a janela ganha um estado mais rico

Lembre do template da janela variável (seção Array): right expande, e um while encolhe left enquanto a janela viola a condição. O esqueleto é idêntico aqui — o que muda é o que a janela carrega e o que conta como violação.

left = 0
contagem = {}            # ← o estado agora é um mapa de frequência
para right de 0 até n-1:
    contagem[s[right]] += 1            # char entra pela direita
    enquanto a janela é INVÁLIDA:
        contagem[s[left]] -= 1         # char sai pela esquerda
        left += 1
    registre o melhor (janela [left..right] é válida)

A definição de "inválida" muda por problema: tem char repetido?, precisa trocar mais que k chars?, ainda falta cobrir alguma letra do alvo?. Tudo isso é lido a partir do mapa de contagens.

E o porquê do O(n) é o mesmo da seção Array: cada caractere entra na janela uma vez (right) e sai no máximo uma vez (left) — no máximo 2n movimentos, cada um O(1). O while interno não faz disso um O(n²).

Os sinais no enunciado

"substring (contígua!) mais longa/mais curta que satisfaz ..." .
Uma condição sobre os caracteres dentro da janela ("sem repetição", "no máximo k distintos", "contém todas as letras de t").
Diferença crucial para a aula anterior: aqui a ordem e a contiguidade importam (é uma substring), não só a composição.

Exemplo 1 — Longest Substring Without Repeating Characters

"Maior substring sem caracteres repetidos." A condição de validade: nenhuma letra aparece duas vezes na janela.

Força bruta: testar todas as substrings e checar repetição — O(n²) ou O(n³).
O desperdício: ao mover o início, recomeçamos a verificação do zero.
O padrão: expanda right sempre; se o novo char já está na janela, encolha left até remover a repetição. O estado é o conjunto de chars da janela.

Veja a janela [left..right] crescendo e encolhendo — repare que left só avança quando right traz um caractere repetido:

Execução real, gravada passo a passo

Carregando Python no navegador (primeira vez demora alguns segundos)…

A janela sempre contém caracteres únicos, e a resposta é o maior tamanho right - left + 1 visto. O(n) de tempo; espaço O(min(n, alfabeto)) para o mapa.

Exemplo 2 — Longest Repeating Character Replacement

"Maior substring que vira um bloco de uma letra só trocando no máximo k caracteres." A condição de validade fica mais sutil:

tamanho da janela − (contagem do caractere mais frequente nela) ≤ k

Ou seja: os caracteres que não são o majoritário são os que você teria de trocar; se forem ≤ k, a janela é válida. O mapa de contagens é o que permite saber, em O(1), qual é o caractere mais frequente da janela.

Carregando editor…

Por que é O(n)?

Uma passada de right (n vezes); left nunca recua. As operações no mapa e o max são O(1). Mesmo argumento de progresso irreversível da seção Array: cada char entra e sai no máximo uma vez. O(n), espaço O(1) (alfabeto fixo).

Exemplo 3 — Minimum Window Substring (o boss da seção)

"Menor substring de s que contém todas as letras de t (com multiplicidade)." É o sliding window com frequência no seu auge:

Monte a frequência alvo (de t).
Expanda right, contando os caracteres da janela.
Quando a janela cobre todo o alvo, tente encolher left ao máximo sem perder a cobertura — registrando a menor janela válida.

Aqui a janela quer ser mínima (não máxima): o while de encolhimento roda enquanto a janela continua válida, ao contrário dos exemplos anteriores. É a mesma estrutura, com a direção da otimização invertida — bom sinal de que você entendeu o padrão, não decorou um caso.

Variante	Janela cresce até...	Janela encolhe enquanto...	Quer
Sem repetição	sempre	há repetição	máxima
≤ k trocas	sempre	precisa de >k trocas	máxima
Cobrir `t`	cobrir o alvo	continua cobrindo	mínima

Sliding window ou contagem fixa? (aula 2 vs aula 3)

A composição da string inteira importa (anagrama, agrupar)? → contagem fixa (aula 2).
A condição é sobre uma substring contígua que cresce/encolhe? → sliding window (esta aula).

🧠 Quiz de fixação

0/4

1. O que muda no sliding window quando passamos de arrays para strings como nestes problemas?

2. Mesmo com um while interno encolhendo a janela, por que esses algoritmos são O(n)?

3. No Longest Repeating Character Replacement, por que a condição de validade é '(tamanho da janela − char mais frequente) ≤ k'?

4. No Minimum Window Substring queremos a MENOR janela. Como isso muda o encolhimento em relação aos outros exemplos?

Resumo

Sliding window de string = template do Array + estado = mapa de frequência.
A "validade" da janela é lida do mapa: sem repetição / ≤ k trocas / cobre o alvo.
O(n) sempre, pelo mesmo argumento: cada char entra e sai no máximo uma vez.
Janela máxima encolhe ao violar; janela mínima encolhe enquanto vale.

Próxima aula: voltando aos dois ponteiros — desta vez para palíndromos.

Todas as aulas da seção