Janela Deslizante para Substrings
Implemente a janela deslizante de tamanho variável para encontrar a maior substring sem caracteres repetidos e a menor janela que contenha todos os caracteres-alvo.
Janela Deslizante para Substrings é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O conceito da janela deslizante
Uma janela deslizante mantém um subvetor (ou subcadeia) entre um ponteiro esquerdo e um ponteiro direito. Em vez de recalcular as propriedades de cada subvetor possível do zero em O(n²), a janela se expande para a direita adicionando um elemento e se contrai pela esquerda removendo um elemento, mantendo um estado acumulado em O(1) por etapa. O resultado é um algoritmo O(n). A janela é chamada de “deslizante” porque avança pelo vetor sem voltar.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Tamanho fixo versus variável da janela
Há duas variantes de janela deslizante. Em uma janela de tamanho fixo, os dois ponteiros avançam no mesmo ritmo e a janela sempre contém exatamente k elementos. Em uma janela de tamanho variável, o ponteiro direito se expande de forma gananciosa, e o ponteiro esquerdo só se contrai quando a janela viola uma restrição. Janelas de tamanho variável resolvem problemas como “maior subcadeia sem caracteres repetidos”, nos quais o tamanho ideal da janela não é conhecido antecipadamente.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2Maior subcadeia sem repetições
Este é o problema mais conhecido de janela deslizante variável. Use um conjunto para acompanhar os caracteres da janela atual. Expanda para a direita; quando encontrar uma repetição, reduza a janela pela esquerda até remover o caractere repetido. Uma versão mais rápida usa uma tabela de dispersão que armazena o índice mais recente de cada caractere, permitindo que o ponteiro esquerdo salte além da repetição em uma única etapa, em vez de avançar gradualmente.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')Subcadeia de janela mínima
Dadas as strings s e t, encontre a menor janela em s que contenha todos os caracteres de t. Use dois mapas de frequências: need (caracteres necessários) e have (caracteres da janela atual que atendem ao requisito). Acompanhe quantos caracteres distintos de t foram satisfeitos (contador formed). Expanda para a direita para incluir caracteres; quando toda t estiver coberta, contraia pela esquerda para minimizar a janela. Tempo O(|s| + |t|).
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'Modelo de janela deslizante
A maioria dos problemas de janela deslizante variável segue um modelo: expanda para a direita para incluir o novo caractere, atualize o estado da janela, verifique a validade e, se estiver inválida, reduza pela esquerda até voltar a ser válida. A ideia principal é que o ponteiro esquerdo só avança — nunca volta —, portanto o trabalho total de todas as etapas de redução é O(n). A janela visita cada elemento no máximo duas vezes: uma vez ao adicioná-lo e outra ao removê-lo.
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return bestPermutação em uma string
Verifique se alguma permutação do padrão p aparece como subcadeia de s. Verificar uma permutação equivale a verificar se existe uma janela com as mesmas frequências de caracteres que p. Mantenha uma janela deslizante com exatamente len(p) caracteres e compare as contagens de frequências. Comparar objetos inteiros de contador a cada etapa custa O(26), que é constante para o inglês em minúsculas, resultando em O(n × 26) = O(n) no total.
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # FalseSubcadeias anagramas: conte todas
Encontre todos os índices iniciais dos anagramas de p em s. Esta é a mesma técnica de janela fixa usada para permutação em string, mas, em vez de retornar verdadeiro na primeira correspondência, coletamos todas as posições correspondentes. O tamanho da janela é fixo em len(p); deslizamos a janela por s e comparamos as contagens de frequências em cada etapa.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]Maior subcadeia com no máximo 2 caracteres distintos
Uma variante da janela deslizante: encontre a maior subcadeia que contenha no máximo 2 caracteres distintos. Mantenha um mapa de frequências dos caracteres da janela atual. Quando o mapa tiver mais de 2 entradas, mova o ponteiro esquerdo para a direita, diminuindo a frequência e excluindo o caractere quando ela chegar a zero, até que a restrição seja restaurada. Este é um caso especial do problema “no máximo k caracteres distintos”, com k=2.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')Máximo em uma janela deslizante
Encontre o máximo em cada janela de tamanho k. Verificar à força o máximo de cada janela custa O(n×k). A abordagem ideal usa uma fila dupla monotônica de índices: mantenha uma fila dupla decrescente para que a frente contenha sempre o índice do máximo da janela atual. Remova da frente os índices que saírem da janela e remova de trás os índices quando entrar um elemento maior. O tempo total é O(n).
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Quando usar a janela deslizante
Considere usar a janela deslizante quando encontrar:
- Uma subcadeia ou um subvetor com uma restrição (comprimento máximo, soma = k, no máximo k caracteres distintos)
- Um tamanho fixo de janela com uma agregação (máximo, soma, frequência)
- Perguntas sobre intervalos contíguos, não subconjuntos arbitrários
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2Contagem de janelas válidas: no máximo K
Alguns problemas pedem o número de subvetores que satisfazem uma condição. Um truque útil é contar os subvetores com no máximo k caracteres distintos e depois subtrair para obter exatamente k: exactly(k) = at_most(k) - at_most(k-1). Cada chamada a at_most custa O(n), resultando em O(n) no total. A função at_most conta as janelas em que o número de caracteres distintos não excede k, somando right - left + 1, que representa todos os pontos iniciais esquerdos válidos para cada posição direita.
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: a janela deslizante elimina O(n²) ao manter um estado acumulado da janela, atualizado em O(1) conforme os elementos entram e saem; janelas de tamanho fixo avançam os dois ponteiros no mesmo ritmo, enquanto janelas de tamanho variável se expandem gananciosamente para a direita e se contraem pela esquerda apenas quando uma restrição é violada; e subcadeia de janela mínima e permutação em string usam um estado de janela baseado em mapas de frequências, com um contador que acompanha quantos caracteres necessários estão satisfeitos no momento. Em seguida, exploraremos anagramas e mapas de frequências de caracteres.
Perguntas Frequentes
A aula “Janela Deslizante para Substrings” é grátis?
Sim — o texto completo de “Janela Deslizante para Substrings” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Janela Deslizante para Substrings”?
Implemente a janela deslizante de tamanho variável para encontrar a maior substring sem caracteres repetidos e a menor janela que contenha todos os caracteres-alvo. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Janela Deslizante para Substrings”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- API de Strings do Python para Entrevistas
- Janela Deslizante para Substrings
- Anagramas e Mapas de Frequência de Caracteres
- Codificação, Reversão e Palíndromos de Strings