Minimum Window Substring

Q: O que o contador ausente conta?

É o número de cópias de caracteres que t exige e que a janela ainda não contém, ou seja, a soma dos valores positivos em need . Ele começa com o tamanho de t e é 0 exatamente quando a janela contém todos os caracteres de t . Cópias excedentes nunca o alteram, o que permite substituir uma varredura de todas as letras por uma única comparação.

Q: Em que o problema da menor substring que contém todos os caracteres difere de encontrar um anagrama em uma string?

Um anagrama contém exatamente as letras de t e nenhuma outra, então a janela tem um comprimento fixo de m e desliza uma etapa por vez. Aqui, a janela pode conter caracteres extras, então seu comprimento faz parte da resposta: ela cresce pela direita até cobrir t e encolhe pela esquerda enquanto ainda o cobre.

DifícilJanela deslizante Hashing

+10

Você recebe duas strings, s e t. Encontre a substring mais curta de s, uma sequência de caracteres consecutivos, que contenha cada caractere de t, contando as repetições: se t contiver uma letra duas vezes, a substring deverá contê-la pelo menos duas vezes. A ordem não importa, e a substring também pode conter outros caracteres.

Se várias substrings tiverem o mesmo comprimento mínimo, retorne a mais à esquerda. Se nenhuma substring de s contiver todos os caracteres de t, retorne uma string vazia.

Função

minWindow(s: string, t: string) → string

sstring: a string na qual 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 × 10⁴
1 ≤ t.length ≤ 10⁴
s e t contêm apenas letras do alfabeto inglês. Letras maiúsculas e minúsculas são caracteres diferentes.
Quando várias substrings forem as mais curtas, a resposta será a que aparece mais à esquerda; quando nenhuma existir, será "".

Exemplos

Entrada: s = "mappingtheplan"t = "nap"
Saída: "plan"
Explicação: Lendo da esquerda para a direita, a primeira janela que contém um n, um a e um p é appin, com cinco caracteres. plan, no final, contém os três em quatro caracteres, e nenhuma sequência de três caracteres os contém.

Entrada: s = "banana"t = "aan"
Saída: "ana"
Explicação: t pede duas cópias de a e uma de n. ana no índice 1 contém exatamente isso. Uma segunda ana começa no índice 3, e a mais à esquerda vence.

Entrada: s = "Coddy"t = "cd"
Saída: ""
Explicação: O único C em Coddy é maiúsculo, e letras maiúsculas e minúsculas são caracteres diferentes. Nenhuma substring contém um c minúsculo, então a resposta é a string vazia.

+17 testes ocultos ao enviar

Para ir além

Quando t usa apenas algumas letras e s é longo, a maior parte de s nunca pode importar. 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.

0 de 3 abertas

Solução

A resposta depende de quantos caracteres de cada tipo uma janela contém, não da ordem deles, e a melhor janela pode começar em qualquer lugar. Tentar cada início com cada fim significa O(n²) janelas. O que resolve isso é uma janela cujas bordas só avançam: a borda direita a amplia até que ela cubra t, a esquerda a reduz enquanto ainda cobre t, e um contador de caracteres faltantes indica em uma única etapa se ela cobre t.

Expanda uma janela a partir de cada início

Correta, mas não termina nos maiores testes

Intuição

Encontre onde começa a substring. Depois, aumente-a um caractere por vez, mantendo a contagem de cada caractere dentro dela e, após cada etapa, verifique se ela cobre t: para cada uma das u letras diferentes usadas por t, a janela deve conter pelo menos tantas cópias quanto t. O primeiro fim que satisfizer essa condição fornece a janela de cobertura mais curta para esse início, porque todas as janelas mais curtas com o mesmo início foram verificadas antes e não satisfizeram a condição. Pare nesse ponto.

Faça isso para cada início e mantenha a janela mais curta. Os inícios são testados da esquerda para a direita, e uma janela substitui a melhor apenas quando é estritamente mais curta; assim, entre janelas de mesmo comprimento, a que começa mais à esquerda permanece.

Isso é lento quando as janelas são longas ou não existem. Se o único Z em s estiver bem no final e t exigir um, cada início percorre tudo até o fim: cerca de n²/2 etapas, o que equivale a 1.25 × 10^9 para n = 5 × 10^4, cada uma com uma verificação de até 52 letras. O mesmo acontece quando não existe janela alguma.

Algoritmo

Conte quantas cópias de cada caractere t solicita e liste as letras que ele usa.
Para cada start, limpe uma tabela de contagens e mova end de start até o fim de s, adicionando s[end] à tabela.
Após cada adição, verifique cada letra de t. Se a janela tiver o suficiente de cada uma, compare seu comprimento com o melhor até então, mantenha-a se for estritamente menor e pare de expandir.
Depois de todos os pontos iniciais, retorne a melhor janela ou "" se nenhuma cobrir t.

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

Dois fatos eliminam a necessidade de reiniciar. Adicionar caracteres a uma janela que contém t faz com que ela continue contendo t, e remover caracteres de uma janela que não contém algo faz com que ela continue não contendo. Portanto, quando o início avança para a direita, o fim da menor janela que contém t só pode ficar onde está ou avançar para a direita. As duas extremidades podem avançar juntas, e nenhuma delas volta para trás.

Mova right por s, adicionando cada caractere a uma tabela de contagens. Sempre que a janela contiver t, ela é uma candidata: registre-a se for menor que a melhor até então, depois remova s[left], avance left e verifique novamente. Repita até que a janela deixe de conter t; então, volte a expandir pela direita.

Nenhuma janela passa despercebida. Considere a melhor janela, de L a R. Se left tivesse passado de L antes de right chegar a R, alguma janela começando em L e terminando antes de R teria contido t e seria menor que a melhor. Portanto, quando right chega a R, o laço de redução avança left até L e registra a melhor janela. Cada extremidade se move no máximo n vezes, mas cada verificação lê até u contagens, uma para cada letra usada por t, embora apenas uma contagem tenha mudado desde a última verificação.

Algoritmo

Conte as ocorrências que t exige e liste suas letras; comece com uma janela vazia, left = 0 e o melhor comprimento igual a n+1.
Mova right por todos os índices e adicione s[right] às contagens da janela.
Enquanto a janela tiver ocorrências suficientes de cada letra de t, registre a janela se ela for estritamente menor que a melhor, remova s[left] das contagens e avance left.
Retorne a melhor janela ou "" se o melhor comprimento ainda for n+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

Mantenha a mesma janela e substitua a verificação por um número. Seja need[c] a quantidade de ocorrências de c que t exige menos a quantidade dentro da janela. Um valor positivo significa que ainda faltam algumas ocorrências na janela; um valor negativo significa que há ocorrências sobrando. Seja missing a quantidade total de ocorrências que faltam na janela, que começa com o comprimento de t. A janela contém t exatamente quando missing é 0.

Atualizá-lo custa uma etapa. Quando s[right] entra e o valor de need para ele é maior que 0, ele preenche uma lacuna, então missing diminui em um; de qualquer forma, need diminui em um e pode ficar abaixo de 0, indicando uma ocorrência sobrando. Quando s[left] sai, need aumenta em um e, se agora for maior que 0, a janela perdeu uma ocorrência necessária para t, então missing aumenta em um. As ocorrências sobrando entram e saem sem afetar missing.

Acompanhe s = banana, t = aan: need começa com a 2, n 1 e missing com 3. b não é necessário. O primeiro a reduz missing para 2, o n para 1, e o segundo a para 0, então bana contém t. Ao encolher, removemos o b que sobrava e ficamos com ana, três caracteres, o novo melhor resultado. Remover esse a faz missing voltar a 1. O último a faz a janela conter t novamente, com nana, que encolhe até o segundo ana. Ele não é mais curto, então o ana mais à esquerda permanece.

Cada caractere de s entra na janela uma vez e sai no máximo uma vez, e cada movimento custa uma quantidade fixa de trabalho. A construção de need percorre t uma vez. A execução inteira é O(n + m), com uma tabela de 128 contagens como única memória adicional.

Algoritmo

Preencha need com as contagens de t e defina missing como o comprimento de t, left = 0 e o melhor comprimento como n+1.
Para cada right: se need[s[right]] for maior que 0, diminua missing; em seguida, diminua need[s[right]].
Enquanto missing for 0, registre a janela se ela for estritamente menor que a melhor. Em seguida, aumente need[s[left]]; se agora for maior que 0, aumente missing. Avance left.
Retorne a melhor janela ou "" se o melhor comprimento ainda for n+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

A maioria das respostas erradas conta a coisa errada ou registra a janela no momento errado.

Contar letras em vez de cópias. t = aan precisa de dois as, então ban não cobre isso.
Diminuir missing para cada caractere que entra. Um terceiro a é excedente; se ele diminuir missing, o contador chega a 0 enquanto a janela ainda não contém o n. Diminua-o somente quando need for maior que 0.
Aumentar missing para cada caractere que sai. Remover um excedente mantém a janela cobrindo t; aumente-o somente quando need ficar maior que 0.
Registrar a janela depois do loop de redução. Nesse ponto, ela já não cobre t. Registre-a dentro do loop, antes de remover s[left].
Substituir a melhor janela quando a nova tiver o mesmo comprimento. Isso retorna a janela mais à direita entre as mais curtas; compare usando menor que estrito.
Usar n como comprimento para “não encontrado”. Quando a resposta for todo o s, o comprimento também será n. Comece em n+1 para que os dois casos sejam diferentes.
Uma tabela de 26 posições indexada por c - 'a'. Letras maiúsculas ficam fora dela. Use uma posição para cada código de caractere.

Perguntas frequentes4

Qual é a complexidade de tempo do problema Minimum Window Substring?

A janela deslizante com um contador de caracteres faltantes tem complexidade de 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, com um custo fixo por movimento. A memória extra é uma tabela com uma contagem por código de caractere, que não aumenta com a entrada.

Por que a borda esquerda nunca se move para trás?

A borda esquerda passa de uma posição somente depois que uma janela iniciada ali cobre t, e essa era a menor janela que cobre t a partir daquele início. Qualquer janela que comece ali e termine mais adiante é maior, então voltar nunca poderia encontrar uma resposta melhor. É por isso que as duas bordas avançam uma única vez e o trabalho permanece linear.

O que o contador ausente conta?

É o número de cópias de caracteres que t exige e que a janela ainda não contém, ou seja, a soma dos valores positivos em need. Ele começa com o tamanho de t e é 0 exatamente quando a janela contém todos os caracteres de t. Cópias excedentes nunca o alteram, o que permite substituir uma varredura de todas as letras por uma única comparação.

Em que o problema da menor substring que contém todos os caracteres difere de encontrar um anagrama em uma string?

Um anagrama contém exatamente as letras de t e nenhuma outra, então a janela tem um comprimento fixo de m e desliza uma etapa por vez. Aqui, a janela pode conter caracteres extras, então seu comprimento faz parte da resposta: ela cresce pela direita até cobrir t e encolhe pela esquerda enquanto ainda o cobre.

Python

def minWindow(s, t):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "mappingtheplan"
t = "nap"

Esperado

"plan"

Minimum Window Substring

Função

Restrições

Exemplos

Dicas

Solução

Expanda uma janela a partir de cada início

Janela deslizante que verifica cada letra

Janela deslizante com um contador de elementos faltantes

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos