Minimum Window Substring
Você recebe duas strings, s e t. Encontre a substring mais curta de s que contenha todos os caracteres de t, contando as repetições: se t tiver uma letra duas vezes, a substring deverá tê-la pelo menos duas vezes. A ordem não importa, e outros caracteres também podem aparecer.
Se várias substrings forem as mais curtas, retorne a que aparece mais à esquerda. Se nenhuma contiver todos os caracteres de t, retorne uma string vazia.
Função
- sstring
- a string em que pesquisar
- tstring
- os caracteres que a janela deve conter, incluindo repetições
- Retornastring
- a substring mais curta e, em caso de empate, mais à esquerda de s que contém todos os caracteres de t, ou uma string vazia
Restrições
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104setcontêm apenas letras do inglês. Letras maiúsculas e minúsculas são caracteres diferentes.- Quando várias substrings forem as mais curtas, a resposta é a mais à esquerda; quando nenhuma existir, é
"".
Exemplos
- Entrada
- s = "mappingtheplan"t = "nap"
- Saída
- "plan"
- Explicação
- A primeira janela da esquerda que contém um
n, umae umpéappin, com cinco caracteres.plancontém os três em quatro caracteres, e nenhuma sequência de três os contém.
- Entrada
- s = "banana"t = "aan"
- Saída
- "ana"
- Explicação
tpede duas cópias deae umn.anano índice 1 contém exatamente isso. Uma segundaanacomeça no índice 3, e a mais à esquerda é escolhida.
- Entrada
- s = "Coddy"t = "cd"
- Saída
- ""
- Explicação
- O
CemCoddyestá em maiúscula, um caractere diferente dec. Nenhuma substring contém umcminúsculo, então a resposta é a string vazia.
Para ir além
Quando t usa poucas letras e s é longo, a maior parte de s nunca importa. Você consegue fazer a janela saltar apenas entre as posições que contêm uma letra de t?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Uma janela que contém todo o
tcontinua contendo quando você a aumenta, e uma janela que deixa algo de fora continua deixando de fora quando você a diminui. Use isso para evitar testar cada início com cada fim.Avance a borda direita até que a janela cubra
t. Em seguida, avance a borda esquerda enquanto a janela ainda cobrirt, registrando-a a cada vez. Nenhuma das bordas precisa voltar.Mantenha uma tabela de quantas cópias a mais de cada caractere a janela precisa e um número,
missing, para indicar quantas cópias faltam no total. Um caractere que entra reduzmissingsomente se ainda era necessário, e um caractere que sai aumenta esse valor somente se a janela ficar com uma quantidade menor do que a necessária. A janela contémtexatamente quandomissingé 0.
Solução
Importam apenas as contagens em uma janela, não a ordem delas. Mova a borda direita até que a janela cubra t e, em seguida, mova a borda esquerda enquanto ela ainda cobrir; nenhuma das bordas volta. Um contador de caracteres ausentes informa, em uma única etapa, se a janela cobre t.
Cresça uma janela a partir de cada início
Correta, mas não termina nos maiores testes
Intuição
Fixe um início e aumente a janela um caractere por vez, mantendo a contagem de cada caractere. Após cada etapa, verifique cada uma das u letras que t usa. O primeiro fim que passar fornece a menor janela que cobre a partir desse início, então pare ali. Os inícios são percorridos da esquerda para a direita, e somente uma janela estritamente menor substitui a melhor, então, em caso de empate, fica a mais à esquerda.
Se nenhuma janela existir, cada início percorre até o fim de s: cerca de n²/2 etapas, 1.25 × 10^9 para n = 5 × 10^4.
Algoritmo
- Conte as ocorrências de cada letra que
texige. - Para cada
start, limpe uma tabela de contagem e movaendpara a direita, adicionandos[end]. - Quando a janela contiver uma quantidade suficiente de cada letra, mantenha-a se for estritamente menor que a melhor e passe para o próximo início.
- Retorne a melhor janela ou
""se nenhuma cobrirt.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
best_start, best_len = 0, len(s) + 1
for start in range(len(s)):
have = [0] * 128 # counts inside s[start..end]
for end in range(start, len(s)):
have[ord(s[end])] += 1
if all(have[c] >= need[c] for c in letters):
# The first end that covers t gives the shortest window from this start.
if end - start + 1 < best_len:
best_start, best_len = start, end - start + 1
break
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]Janela deslizante que verifica cada letra
Intuição
Adicionar caracteres a uma janela que cobre mantém a cobertura, e remover caracteres de uma janela que não contém algo faz com que ela continue sem conter. Portanto, conforme o início se move para a direita, o fim da menor janela que cobre nunca se move para a esquerda.
Nenhuma janela é ignorada. Considere a melhor janela, de L a R. Para left passar de L antes de right chegar a R, uma janela menor a partir de L teria que cobrir t. Portanto, quando right chega a R, o encolhimento move left até L e a registra.
Cada extremidade se move no máximo n vezes, mas cada verificação lê até u contagens: O(n·u).
Algoritmo
- Conte as ocorrências de
tnecessárias; definaleft = 0e o melhor comprimento comon+1. - Para cada
right, adiciones[right]às contagens da janela. - Enquanto houver ocorrências suficientes de cada letra de
t, registre a janela se ela for estritamente menor, removas[left]e avanceleft. - Retorne a melhor janela ou
""se o melhor comprimento ainda forn+1.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
have = [0] * 128 # counts inside s[left..right]
def covers():
for c in letters:
if have[c] < need[c]:
return False
return True
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
have[ord(s[right])] += 1 # expand on the right
while covers(): # shrink from the left while the window still covers t
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
have[ord(s[left])] -= 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]Janela deslizante com um contador de elementos faltantes
Intuição
Substitua a varredura por um único número. Seja need[c] a quantidade de ocorrências de c que t exige menos a quantidade de ocorrências na janela; um valor negativo significa que há ocorrências sobrando. Seja missing a quantidade de ocorrências que ainda faltam na janela, começando pelo comprimento de t. A janela cobre t exatamente quando missing é 0.
Um caractere que entra enquanto seu need está acima de 0 preenche uma lacuna, então missing diminui. Um caractere cuja remoção faz need ficar acima de 0 abre uma lacuna, então missing aumenta. As ocorrências sobrando não o afetam. Em banana, com t = aan, missing chega a 0 pela primeira vez em bana, e remover o b excedente deixa ana ainda cobrindo.
Cada caractere entra e sai uma vez, com custo constante: tempo O(n + m), com uma tabela de 128 contagens.
Algoritmo
- Preencha
needcom as contagens det; definamissingcomo o comprimento det,left = 0e o melhor comprimento comon+1. - Para cada
right: seneed[s[right]]for maior que 0, diminuamissing; em seguida, diminuaneed[s[right]]. - Enquanto
missingfor 0, registre a janela se ela for estritamente menor. Aumenteneed[s[left]]; se agora for maior que 0, aumentemissing. Avanceleft. - Retorne a melhor janela ou
""se o melhor comprimento ainda forn+1.
def minWindow(s, t):
# need[c]: copies of c that t asks for minus copies inside the window.
# Positive means the window still lacks c; negative means it holds spares.
need = [0] * 128
for ch in t:
need[ord(ch)] += 1
missing = len(t) # characters of t the window does not cover yet
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
c = ord(s[right])
if need[c] > 0: # this copy fills a gap
missing -= 1
need[c] -= 1
while missing == 0: # the window covers t: record it, then shrink
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
c = ord(s[left])
need[c] += 1
if need[c] > 0: # gave away a copy t needs
missing += 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]
Armadilhas e casos extremos
- Contar letras em vez de cópias.
t = aanprecisa de doisas, entãobannão atende a isso. - Alterar
missingpara cada caractere que entra ou sai. Umaexcedente é contado, emissingpode chegar a 0 enquanto a janela não contém on. - Substituir a melhor janela quando o comprimento é igual. No segundo exemplo, isso retorna o
anano índice 3. - Usar
ncomo comprimento para “não encontrado”. Quando a resposta é toda as, seu comprimento também én; comece den+1. - Uma tabela de 26 posições indexada por
c - 'a'. Letras maiúsculas, como no terceiro exemplo, ficam fora dela.
Perguntas frequentes3
Qual é a complexidade de tempo de Minimum Window Substring?
A janela com contador de caracteres ausentes é executada em tempo O(n + m), em que n e m são os comprimentos de s e t. A construção da tabela lê t uma vez, e cada caractere de s entra e sai da janela no máximo uma vez. A memória extra é de uma contagem por código de caractere.
Por que a borda esquerda nunca volta?
A borda esquerda só ultrapassa uma posição depois que a janela iniciada ali abrange t, e essa janela era a menor que abrangia t a partir daquele início. Qualquer janela que comece ali e termine mais tarde é maior, então voltar nunca pode encontrar uma resposta melhor.
Como Minimum Window Substring é diferente de encontrar um anagrama em uma string?
Um anagrama contém exatamente as letras de t, então sua janela tem comprimento fixo m e desliza uma posição de cada vez. Aqui, caracteres extras são permitidos, então o comprimento faz parte da resposta: a janela cresce até cobrir t e encolhe enquanto ainda o cobre.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def minWindow(s, t):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
s = "mappingtheplan" t = "nap"
Saída Esperada
"plan"