A Técnica de Sliding Window: Um Padrão de Entrevista Whiteboard

Eu já estive dos dois lados da mesa de entrevista técnica, na maior parte das vezes como candidato. A técnica de sliding window aparece constantemente, e ela separa candidatos que internalizaram um padrão de candidatos que estão tentando derivar a solução do zero sob pressão. Os primeiros terminam cedo e explicam seu pensamento. Os segundos ficam sem tempo. Aqui está como chegar à primeira posição.

O Que o Padrão Realmente É

Sliding window é uma otimização para problemas envolvendo sequências contíguas: subarrays ou substrings. A abordagem ingênua para a maioria desses problemas é um loop aninhado que reexamina elementos sobrepostos em cada iteração, dando tempo O(n ao quadrado). O sliding window evita isso mantendo um intervalo com dois ponteiros e atualizando o estado incrementalmente conforme o intervalo se move. A maioria dos problemas cai para O(n).

Existem duas variantes. Janelas de tamanho fixo: o comprimento da janela é dado. Janelas dinâmicas: você expande e encolhe baseado em uma restrição. Identificar qual variante você está lidando é a primeira decisão em qualquer problema de entrevista que se encaixa nesse padrão.

Quando Usar Esse Padrão

• O problema envolve um subarray ou substring contígua
• Pede-se para encontrar um máximo, mínimo ou agregado sobre todas as janelas de um tamanho dado
• Você está procurando a substring mais longa ou mais curta que satisfaz uma restrição
• A solução de força bruta tem loops aninhados iterando sobre o mesmo array ou string
• O problema menciona uma 'janela', 'intervalo' ou elementos 'consecutivos'

Janela Fixa: Soma Máxima de Subarray de Tamanho K

Este é o ponto de entrada para o padrão. Dado um array de inteiros e um número k, encontre a soma máxima de qualquer subarray contíguo de comprimento k. A abordagem ingênua soma k elementos para cada posição inicial: O(n vezes k). O sliding window adiciona o elemento que entra e remove o que sai, mantendo uma soma corrente: O(n).

function maxSumSubarray(nums: number[], k: number): number {
  if (nums.length < k) return 0;

  // Build the first window
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let maxSum = windowSum;

  // Slide the window: add incoming, subtract outgoing
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }

  return maxSum;
}

console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (indices 2-4: 5+1+3)
console.log(maxSumSubarray([2, 3, 4, 1, 5], 2));    // 7 (3+4)

A operação chave é windowSum += nums[i] - nums[i - k]. Você não está recalculando do zero. Está deslizando: adiciona o novo elemento à direita, remove o antigo à esquerda. Essa única linha é todo o insight da janela fixa.

Uma linha desse código é uma decisão, não um detalhe. Retornar 0 quando o array é menor que k devolve um valor que uma janela real também poderia produzir, então quem chama não consegue distinguir 'nenhuma janela válida' de 'a melhor janela soma zero'. Eu retorno 0 aqui para manter o exemplo curto. Em uma entrevista, diga isso em voz alta e escolha de propósito: lançar erro em entrada inválida, retornar null, ou perguntar ao entrevistador qual deveria ser o contrato. Perceber que um valor sentinela colide com uma resposta legítima é exatamente o tipo de coisa que eles estão ouvindo.

Janela Dinâmica: Maior Substring Sem Caracteres Repetidos

Janelas dinâmicas exigem decidir quando encolher. Neste problema a restrição é unicidade: cada caractere na janela deve aparecer uma vez. Expanda o ponteiro direito livremente. Quando um duplicado entra na janela, avance o ponteiro esquerdo até o duplicado sair.

function lengthOfLongestUniqueSubstring(s: string): number {
  const lastSeen = new Map<string, number>();
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // If we've seen this char and it's inside the current window, jump left past it
    if (lastSeen.has(char) && lastSeen.get(char)! >= left) {
      left = lastSeen.get(char)! + 1;
    }

    lastSeen.set(char, right);
    maxLength = Math.max(maxLength, right - left + 1);
  }

  return maxLength;
}

console.log(lengthOfLongestUniqueSubstring('abcabcbb')); // 3 (abc)
console.log(lengthOfLongestUniqueSubstring('pwwkew'));   // 3 (wke)

Guardar o último índice visto em vez de apagar entradas do map permite que left salte direto para a posição correta em vez de andar caractere por caractere. Seja preciso sobre o que isso te dá, porque um entrevistador vai conferir. As duas versões são O(n). Na versão que anda de um em um, o ponteiro left ainda se move no máximo n vezes ao longo de todo o loop, então o trabalho total é linear nos dois casos. O salto economiza operações de map e um fator constante, não uma classe de complexidade.

O Template Reutilizável

A maioria dos problemas de janela dinâmica segue a mesma estrutura. Internalizar esse template significa que você gasta o tempo de entrevista na lógica específica do problema, não no scaffolding que já resolveu antes.

function dynamicWindowTemplate(input: string | number[]): number {
  let left = 0;
  let result = 0;
  const windowState = new Map<string | number, number>();

  for (let right = 0; right < input.length; right++) {
    const incoming = input[right];

    // 1. Add incoming element to window state
    windowState.set(incoming, (windowState.get(incoming) ?? 0) + 1);

    // 2. Shrink window while constraint is violated
    while (/* window constraint violated */ false) {
      const outgoing = input[left];
      const count = windowState.get(outgoing)! - 1;
      if (count === 0) {
        windowState.delete(outgoing);
      } else {
        windowState.set(outgoing, count);
      }
      left++;
    }

    // 3. Update result with current valid window
    result = Math.max(result, right - left + 1);
  }

  return result;
}

Reconhecendo o Padrão em uma Entrevista

• O problema diz 'subarray', 'substring' ou 'contíguo'? Sliding window é o padrão candidato.
• K é dado? Janela fixa. Existe uma restrição a satisfazer? Janela dinâmica.
• A solução de força bruta requer loops aninhados sobre os mesmos dados? Você está vendo O(n ao quadrado) e sliding window vai resolver.
• Você consegue descrever o problema como: encontre o intervalo ótimo que satisfaz alguma condição? É um problema de sliding window.

Em uma entrevista whiteboard, nomear o padrão em voz alta antes de escrever código sinaliza reconhecimento de padrões. Esse é um dos sinais mais valorizados que um entrevistador procura.

Pratique o problema de soma máxima com janela fixa e o de maior substring única com janela dinâmica até que pareçam mecânicos. Esses dois cobrem as duas variantes estruturais. Todo outro problema de sliding window que você encontrar em uma entrevista é uma variação de um deles. Uma vez que o template está internalizado, o tempo de entrevista vai para a lógica específica da restrição, que é a parte que realmente testa habilidade de resolução de problemas.

Referências

• LeetCode. Sliding Window Problems. https://leetcode.com/tag/sliding-window/
• GeeksforGeeks. Sliding Window Technique. https://www.geeksforgeeks.org/window-sliding-technique/
• MDN Web Docs. JavaScript Array. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array