Sliding Window

Conceito

Sliding window é 4. Dois Ponteiros no mesmo sentido, com um estado da janela que você mantém atualizado incrementalmente.

A ideia central, e a única que importa: ao mover a janela, você não recalcula. Você remove a contribuição do elemento que saiu e adiciona a do que entrou. Isso é o que transforma O(n·k) em O(n).

[1 2 3] 4 5    soma = 6
1 [2 3 4] 5    soma = 6 - 1 + 4 = 9   <- duas operações, não três

Recalcular a soma da janela a cada passo custa O(k) por passo → O(n·k). Atualizar incrementalmente custa O(1) por passo → O(n).

Janela fixa: tamanho k constante; os dois lados se movem juntos. Direto.

Janela variável: o padrão mais poderoso, e o que parece quadrático e não é:

para cada direita:
    expande: inclui s[direita] no estado
    enquanto a condição for violada:
        contrai: remove s[esquerda] do estado; esquerda++
    registra a resposta

O laço interno assusta, mas cada elemento entra na janela uma vez e sai no máximo uma vez. O total de movimentos de esquerda ao longo de toda a execução é ≤ n. Logo o algoritmo é O(n) amortizado, não O(n²). Esse argumento é a parte que vale entender — é o mesmo tipo de raciocínio de amortização do append (1. Notação Big-O).

Sinais no enunciado:

• "subarray contíguo" ou "substring" — contiguidade é o requisito; sem ela, é outro problema
• "maior/menor/mais longo/mais curto"
• "no máximo K distintos", "soma ≥ alvo", "sem repetição"

A pergunta de projeto que decide tudo: qual estado a janela precisa manter, e ele é atualizável em O(1)?

O máximo é o caso instrutivo: remover um elemento não te diz qual é o novo máximo. A solução é uma deque monotônica, que mantém candidatos em ordem decrescente — e é a razão de "máximo em janela deslizante" ser um exercício muito mais difícil que "soma em janela deslizante".

Em Go

Sem abstração: dois índices, e um map ou array de contagem para o estado.

Estado como array em vez de mapa: quando o domínio é pequeno e conhecido, um [128]int ou [26]int bate um map com folga — é um array na stack, sem hash e sem alocação. Para janela sobre caracteres ASCII, é a escolha certa.

Para o caso "máximo na janela", Go não tem deque na stdlib; o idioma é um slice de índices usado como deque (append no fim, [1:] no início, com cuidado).

Respostas às perguntas-guia

1. Qual a diferença entre janela de tamanho fixo e janela variável?

Conceito: na fixa, os dois lados andam juntos e o tamanho é invariante. Na variável, a direita expande e a esquerda contrai em resposta a uma condição — o tamanho é a resposta que você está buscando.

Em Go: nada específico; a variável é a que exige o argumento de amortização para você confiar que é O(n).

2. O que entra e o que sai a cada passo — e como manter o estado da janela em O(1)?

Conceept: entra s[direita], sai s[esquerda]. O estado tem que ser decrementável: soma subtrai, contador decrementa (e você remove a chave do mapa quando chega a zero, senão a contagem de distintos fica errada).

Em Go: o detalhe que quebra o algoritmo é justamente esse — cont[c]-- sem delete(cont, c) quando chega a zero faz len(cont) contar chaves com valor 0.

3. Que sinais no enunciado indicam sliding window ("subarray contíguo", "maior/menor")?

Conceito: contiguidade + otimização (maior/menor) + uma condição sobre a janela.

Em Go: se o enunciado é sobre substring, adicione a pergunta "bytes ou runas?" à lista de sinais.

4. Por que ele é um caso particular de 4. Dois Ponteiros?

Conceito: porque são dois índices no mesmo sentido, cada um avançando no máximo n vezes. A única diferença é que sliding window mantém estado agregado entre os dois, em vez de apenas comparar as pontas.

Em Go: mesma consequência prática: nenhuma alocação além do mapa de estado.

Trade-offs

Do conceito:

• O(n) em troca de exigir contiguidade. Se a resposta pode ser um subconjunto esparso, o padrão não se aplica — e usar sliding window aí dá resposta errada, não lenta.
• Estado incremental compra O(1) por passo e cobra a corretude do decremento: errar o "remover a contribuição" é o bug mais comum e o mais difícil de ver.
• Janela variável é O(n) amortizado com laço interno — parece pior do que é, e essa aparência faz gente reescrever para algo pior.

Em Go:

• [128]int como estado não aloca e vence map para domínios pequenos.
• map como estado é geral e exige delete no zero.
• Sobre strings, []rune custa uma alocação e compra corretude; índice de byte é grátis e só vale com ASCII garantido.

Exemplo prático

package main

import "fmt"

// --- Janela FIXA: soma incremental ---
func maiorSomaK(s []int, k int) int {
	if len(s) < k { return 0 }
	soma := 0
	for _, v := range s[:k] { soma += v }
	melhor := soma
	for i := k; i < len(s); i++ {
		soma += s[i] - s[i-k] // ENTRA um, SAI um: O(1), nao O(k)
		if soma > melhor { melhor = soma }
	}
	return melhor
}

// --- Janela VARIÁVEL: menor subarray com soma >= alvo ---
func menorSubarray(s []int, alvo int) int {
	melhor, soma, esq := len(s)+1, 0, 0
	for dir := 0; dir < len(s); dir++ {
		soma += s[dir] // expande
		for soma >= alvo { // contrai enquanto a condição VALE
			if dir-esq+1 < melhor { melhor = dir - esq + 1 }
			soma -= s[esq]
			esq++
		}
	}
	if melhor > len(s) { return 0 }
	return melhor
}

// --- Janela VARIÁVEL com estado de contagem (ASCII: array, nao map) ---
func maiorSemRepetir(s string) (int, string) {
	var visto [128]int // -1 seria "nunca visto"; usamos 0 = ausente
	for i := range visto { visto[i] = -1 }
	melhor, ini, esq := 0, 0, 0
	for dir := 0; dir < len(s); dir++ {
		c := s[dir]
		if visto[c] >= esq { // o caractere já está DENTRO da janela
			esq = visto[c] + 1 // pula a esquerda para depois dele
		}
		visto[c] = dir
		if dir-esq+1 > melhor {
			melhor, ini = dir-esq+1, esq
		}
	}
	return melhor, s[ini : ini+melhor]
}

// --- O delete(cont, c) que muita gente esquece ---
func maiorComKDistintos(s string, k int) int {
	cont := map[byte]int{}
	melhor, esq := 0, 0
	for dir := 0; dir < len(s); dir++ {
		cont[s[dir]]++
		for len(cont) > k {
			c := s[esq]
			cont[c]--
			if cont[c] == 0 {
				delete(cont, c) // SEM isto, len(cont) conta chaves zeradas
			}
			esq++
		}
		if dir-esq+1 > melhor { melhor = dir - esq + 1 }
	}
	return melhor
}

// --- O caso difícil: MÁXIMO na janela precisa de deque monotônica ---
func maximosNaJanela(s []int, k int) []int {
	var deque []int // guarda ÍNDICES, valores em ordem decrescente
	var out []int
	for i, v := range s {
		for len(deque) > 0 && deque[0] <= i-k { // saiu da janela
			deque = deque[1:]
		}
		for len(deque) > 0 && s[deque[len(deque)-1]] <= v {
			deque = deque[:len(deque)-1] // nunca mais será máximo
		}
		deque = append(deque, i)
		if i >= k-1 {
			out = append(out, s[deque[0]]) // o máximo está sempre na frente
		}
	}
	return out
}

func main() {
	s := []int{2, 1, 5, 1, 3, 2}
	fmt.Println("maior soma de 3:", maiorSomaK(s, 3))
	fmt.Println("menor subarray com soma>=7:", menorSubarray([]int{2, 3, 1, 2, 4, 3}, 7))

	n, sub := maiorSemRepetir("abcabcbb")
	fmt.Printf("maior sem repetir: %d (%q)\n", n, sub)
	n, sub = maiorSemRepetir("pwwkew")
	fmt.Printf("maior sem repetir: %d (%q)\n", n, sub)

	fmt.Println("maior com 2 distintos em eceba:", maiorComKDistintos("eceba", 2))
	fmt.Println("máximos em janelas de 3:", maximosNaJanela([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3))

	// bytes vs runas
	texto := "café"
	fmt.Printf("%q: len em bytes=%d, em runas=%d\n", texto, len(texto), len([]rune(texto)))
}

Relacionado

• 4. Dois Ponteiros — o padrão de que este é um caso particular
• 6. Hash Map para Contagem — o estado da janela quase sempre é uma contagem
• 1. Notação Big-O — semana 2, o argumento de amortização que justifica o O(n)
• 5. Fila — semana 2, a deque monotônica é uma fila com regra de descarte

---

Parte de Semana 04 - Algoritmos Essenciais · 00 - MOC Fundamentos de Programação