Permutation in String

Q: Qual é a complexidade de tempo de Permutation in String?

Com uma janela deslizante, a complexidade é O(m + n) , em que m é o comprimento de s1 e n é o comprimento de s2 . Você conta s1 uma vez; depois, cada letra de s2 entra na janela uma vez e sai dela uma vez. Recontar cada janela do zero custa O(n · m) .

Q: Encontrar uma permutação em uma string é o mesmo que encontrar um anagrama dentro de uma string?

Sim. Uma permutação de s1 é um anagrama dela, então a questão é saber se alguma substring de s2 com comprimento m é um anagrama de s1 . A verificação de anagrama entre duas strings completas compara a contagem de letras uma vez; aqui, a mesma comparação é executada em uma janela que desliza por s2 .

Q: Por que a janela deslizante tem tamanho fixo aqui?

Toda permutação de s1 tem exatamente m letras, então apenas janelas de comprimento m podem corresponder. Problemas como o da maior substring sem repetições aumentam e diminuem a janela; aqui, as duas extremidades se movem juntas, uma etapa de cada vez.

MédioJanela deslizante Hashing

+10

Uma permutação de uma string usa as mesmas letras em qualquer ordem, cada uma tantas vezes quanto na original: tar, rat e art são permutações umas das outras. Você recebe duas strings s1 e s2 compostas por letras minúsculas do inglês. Retorne true se alguma permutação de s1 aparecer em s2 como uma substring (uma sequência de caracteres consecutivos) e false caso contrário.

Função

checkInclusion(s1: string, s2: string) → boolean

s1string: as letras para reorganizar
s2string: o texto a ser pesquisado
Retornaboolean: verdadeiro se uma substring de s2 for um rearranjo de s1

Restrições

1 ≤ s1.length ≤ 2 × 10⁴
1 ≤ s2.length ≤ 5 × 10⁴
s1 e s2 contêm apenas letras minúsculas do inglês (a a z).
s1 pode ser mais longo que s2.

Exemplos

Entrada: s1 = "tar"s2 = "smartphone"
Saída: true
Explicação: A substring art nos índices 2 a 4 de smartphone contém um a, um r e um t, as mesmas letras que tar.

Entrada: s1 = "noon"s2 = "onion"
Saída: false
Explicação: As substrings de comprimento 4 são onio e nion. noon precisa de dois ns e dois os, e cada janela tem um i no lugar de uma dessas letras. Todas as letras de noon aparecem em onion, mas nenhuma janela tem as quantidades certas.

Entrada: s1 = "abcd"s2 = "dcb"
Saída: false
Explicação: Qualquer permutação de abcd tem 4 letras, e dcb tem apenas 3, então não pode conter uma.

Para ir além

Você consegue retornar todos os índices de s2 em que começa uma permutação de s1, ainda em tempo O(m + n)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Listar as permutações de s1 é inviável: 10 letras já têm 3.628.800 ordenações. A saída é deixar de se importar com a ordem. Uma substring de s2 é uma permutação de s1 exatamente quando tem o mesmo comprimento m e a mesma contagem de cada letra. Portanto, cada candidata é uma janela de comprimento fixo, e você pode deslizar uma janela por s2, atualizando suas contagens de letras com a entrada de uma letra e a saída de outra a cada passo.

Conte cada janela desde o início

Correta, mas não termina nos maiores testes

Intuição

A abordagem literal, gerar todas as permutações de s1 e procurá-las, falha imediatamente: 20 letras têm mais de 2 × 10^18 ordenações. Em vez disso, inverta a pergunta. Uma substring de s2 é uma permutação de s1 quando tem exatamente m letras e usa cada letra a mesma quantidade de vezes que s1. A ordem das letras dentro dela não importa.

Então, conte as letras de s1 uma vez em uma tabela de 26 números, com índice 0 para a e 25 para z. Depois, pegue cada substring de s2 com comprimento m, conte suas letras em uma nova tabela e compare as duas tabelas. Para tar em smartphone, as janelas são sma, mar, art e assim por diante, e art corresponde: um a, um r, um t.

Isso está correto porque examina cada candidata. É lento porque janelas vizinhas compartilham m-1 letras e você conta todas elas novamente. Com m = 15,000 e n = 50,000, há 35,001 janelas de 15,000 letras cada, cerca de 5 × 10^8 etapas.

Algoritmo

Se s1 for mais longo que s2, retorne false.
Conte as letras de s1 em uma tabela need com 26 zeros.
Para cada índice inicial de 0 a n-m, conte as letras dos m caracteres a partir desse índice em uma nova tabela.
Se essa tabela for igual a need, retorne true.
Depois da última janela, retorne false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26  # need[0] is 'a', need[25] is 'z'
    for ch in s1:
        need[ord(ch) - 97] += 1
    for start in range(n - m + 1):
        # Count the letters of s2[start : start + m] from scratch
        window = [0] * 26
        for i in range(start, start + m):
            window[ord(s2[i]) - 97] += 1
        if window == need:
            return True
    return False

Deslize a janela e compare 26 contagens

Intuição

Duas janelas adjacentes diferem em apenas duas letras. Ao passar de mar para art, remove-se o m à esquerda e adiciona-se o t à direita. Portanto, mantenha uma tabela para a janela atual e atualize-a com um +1 e um -1 a cada passo, em vez de contar novamente m letras.

Preencha need com s1 e window com as primeiras m letras de s2, e compare-as. Depois, para cada i de m a n-1, adicione s2[i], remova s2[i-m] e compare novamente. A janela agora é s2[i-m+1..i], ainda com m letras.

Cada passo custa duas atualizações e uma comparação de 26 números, qualquer que seja o valor de m. Na maior entrada, isso representa cerca de 26 × 50,000 = 1.3 × 10^6 operações, linear em relação ao comprimento de s2. Esta é a solução que a maioria dos entrevistadores espera.

Algoritmo

Se s1 for mais longo que s2, retorne false.
Conte s1 em need e as primeiras m letras de s2 em window.
Se as duas tabelas forem iguais, retorne true.
Para cada i de m a n-1: some 1 para s2[i], subtraia 1 para s2[i-m] e retorne true se as tabelas forem iguais.
Retorne false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    need = [0] * 26
    window = [0] * 26
    for i in range(m):
        need[ord(s1[i]) - 97] += 1
        window[ord(s2[i]) - 97] += 1  # the first window is s2[0 : m]
    if window == need:
        return True
    for i in range(m, n):
        window[ord(s2[i]) - 97] += 1      # s2[i] enters on the right
        window[ord(s2[i - m]) - 97] -= 1  # s2[i - m] leaves on the left
        if window == need:
            return True
    return False

Deslize a janela e acompanhe as letras desequilibradas

Intuição

Comparar 26 números a cada etapa repete trabalho, porque uma etapa altera apenas dois deles. Em vez disso, mantenha uma tabela balance: balance[c] é a quantidade de ocorrências da letra c em s1 menos a quantidade na janela. A janela é uma permutação de s1 exatamente quando todos os 26 saldos são 0. Ao lado da tabela, mantenha unbalanced, o número de letras cujo saldo não é 0, e responda true assim que ele chegar a 0.

O controle tem uma regra. Antes de alterar balance[c], se ele for 0, a letra está prestes a sair do equilíbrio, então some 1 a unbalanced. Depois da alteração, se ele for 0, a letra chegou ao equilíbrio, então subtraia 1. Uma letra que entra na janela diminui seu saldo em 1; uma letra que sai dela aumenta seu saldo em 1. Um saldo que passa de 2 para 1 não aciona nenhuma das verificações, o que está correto: a letra estava desequilibrada e continua assim.

Percorra tar e smartphone. Os saldos começam em a: 1, r: 1, t: 1, então unbalanced é 3. s e m entram e elevam esse valor para 5; em seguida, a entra e leva o saldo de a a 0: 4. r entra (3) enquanto s sai (2). t entra (1) enquanto m sai (0), e a janela art é a resposta.

Você pode testar unbalanced == 0 desde a primeira letra. Enquanto a janela tiver menos de m letras, a soma dos saldos será um número positivo, então pelo menos um deles não será 0. Cada etapa realiza uma quantidade fixa de trabalho, então a varredura completa é O(m + n), e a tabela sempre contém 26 números, o que corresponde a espaço O(1).

Algoritmo

Se s1 for maior que s2, retorne false.
Conte s1 em balance e defina unbalanced como o número de letras com um saldo diferente de 0.
Para cada índice i de s2, subtraia 1 do saldo de s2[i], adicionando 1 a unbalanced se esse saldo era 0 e subtraindo 1 se ele se tornar 0.
Se i ≥ m, adicione 1 ao saldo de s2[i-m] com o mesmo controle.
Se unbalanced for 0, retorne true. Após o loop, retorne false.

def checkInclusion(s1, s2):
    m, n = len(s1), len(s2)
    if m > n:
        return False
    # balance[c]: copies of letter c in s1 minus copies in the window
    balance = [0] * 26
    for ch in s1:
        balance[ord(ch) - 97] += 1
    unbalanced = sum(1 for b in balance if b != 0)
    for i in range(n):
        # s2[i] enters the window on the right
        c = ord(s2[i]) - 97
        if balance[c] == 0:
            unbalanced += 1
        balance[c] -= 1
        if balance[c] == 0:
            unbalanced -= 1
        # s2[i - m] leaves on the left once the window would pass m letters
        if i >= m:
            c = ord(s2[i - m]) - 97
            if balance[c] == 0:
                unbalanced += 1
            balance[c] += 1
            if balance[c] == 0:
                unbalanced -= 1
        if unbalanced == 0:
            return True
    return False

Armadilhas e casos extremos

A maioria das respostas erradas vem das extremidades da janela ou de verificar quais letras aparecem em vez de quantas vezes aparecem.

Verificar apenas se todas as letras de s1 estão na janela. onio contém todas as letras de noon, mas não é uma permutação dele. Compare as contagens.
Remover a letra errada. Quando s2[i] entra, a letra que sai é s2[i-m], então a janela passa a ser s2[i-m+1..i]. Remover s2[i-m+1] deixa uma janela de m-1 letras.
Pular a primeira janela. Se você comparar apenas depois de deslizar, uma permutação no índice 0 nunca será encontrada.
Esquecer o caso em que s1 é mais longo que s2. Em Rust, n - m com comprimentos sem sinal causa underflow, e em Swift o intervalo 0...(n - m) causa uma falha. Retorne false primeiro.
Comparar arrays com == em uma linguagem na qual isso compara referências. Em JavaScript e Dart, dois arrays diferentes nunca são ==; em Java, use Arrays.equals.

Perguntas frequentes3

Qual é a complexidade de tempo de Permutation in String?

Com uma janela deslizante, a complexidade é O(m + n), em que m é o comprimento de s1 e n é o comprimento de s2. Você conta s1 uma vez; depois, cada letra de s2 entra na janela uma vez e sai dela uma vez. Recontar cada janela do zero custa O(n · m).

Encontrar uma permutação em uma string é o mesmo que encontrar um anagrama dentro de uma string?

Sim. Uma permutação de s1 é um anagrama dela, então a questão é saber se alguma substring de s2 com comprimento m é um anagrama de s1. A verificação de anagrama entre duas strings completas compara a contagem de letras uma vez; aqui, a mesma comparação é executada em uma janela que desliza por s2.

Por que a janela deslizante tem tamanho fixo aqui?

Toda permutação de s1 tem exatamente m letras, então apenas janelas de comprimento m podem corresponder. Problemas como o da maior substring sem repetições aumentam e diminuem a janela; aqui, as duas extremidades se movem juntas, uma etapa de cada vez.

def checkInclusion(s1, s2):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

s1 = "tar"
s2 = "smartphone"

Saída Esperada

true

Permutation in String

Função

Restrições

Exemplos

Dicas

Solução

Conte cada janela desde o início

Deslize a janela e compare 26 contagens

Deslize a janela e acompanhe as letras desequilibradas

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos