Longest Substring Without Repeating Characters

+10

Você recebe uma string s. Encontre a substring mais longa, uma sequência de caracteres consecutivos, na qual nenhum caractere apareça duas vezes, e retorne seu comprimento.

Letras maiúsculas e minúsculas são consideradas caracteres diferentes, então a e A não são repetidos.

Função

lengthOfLongestSubstring(s: string) → integer

sstring: a string a ser pesquisada
Retornainteger: o comprimento da substring mais longa sem caracteres repetidos

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras do alfabeto inglês (minúsculas e maiúsculas) e dígitos.
Letras maiúsculas e minúsculas são caracteres diferentes.

Exemplos

Entrada: s = "coddycode"
Saída: 5
Explicação: ycode contém cinco caracteres diferentes. Adicionar d antes dele resulta em dycode, com d aparecendo duas vezes, e nenhuma outra sequência de cinco ou mais caracteres evita uma repetição.

Entrada: s = "racecar"
Saída: 4
Explicação: Tanto race quanto ecar têm quatro letras diferentes. Cada sequência de cinco letras contém a mesma letra duas vezes.

Entrada: s = "a1b2a3b"
Saída: 5
Explicação: Os dígitos também contam como caracteres, então 1b2a3 tem cinco caracteres diferentes. Ambos os trechos de seis contêm um segundo a ou um segundo b.

Para ir além

O que você mudaria se s pudesse conter qualquer caractere Unicode em vez de letras e dígitos?

Solução

Mantenha uma janela: duas bordas ao redor de uma sequência sem caracteres repetidos. A borda direita lê cada caractere uma vez, e a borda esquerda só avança, então uma única passagem encontra, para cada posição final, a sequência mais longa sem repetições que termina ali.

Verifique cada substring

Correta, mas não termina nos maiores testes

Intuição

Teste cada início e fim, e teste cada substring adicionando seus caracteres a um conjunto até que um deles já esteja nele. Cada candidata é testada, então a mais longa válida não pode passar despercebida.

Há cerca de n²/2 substrings, 1.25 × 10^9 para n = 5 × 10^4, e um teste pode ler até n caracteres: O(n³). Aqui, um teste para após no máximo 63 caracteres, já que a string contém apenas 62 caracteres diferentes, mas ainda restam mais de um bilhão de testes.

Algoritmo

Defina best como 0.
Para cada índice inicial, percorra todos os índices finais, do início ao fim da string.
Adicione os caracteres da substring a um conjunto vazio, um por um, e pare no primeiro que já estiver no conjunto.
Se nenhum caractere se repetir e a substring superar best, armazene seu comprimento.
Retorne best.

def lengthOfLongestSubstring(s):
    def has_no_repeat(start, end):
        seen = set()
        for k in range(start, end + 1):
            if s[k] in seen:
                return False
            seen.add(s[k])
        return True

    best = 0
    n = len(s)
    for start in range(n):
        for end in range(start, n):
            if has_no_repeat(start, end):
                best = max(best, end - start + 1)
    return best

Janela deslizante com um conjunto

Intuição

Se abc não tiver repetição, testar abcd exige uma pergunta: d está entre a, b e c? Um conjunto dos caracteres da janela responde isso de uma só vez.

Mova right um passo por vez. Se o novo caractere estiver no conjunto, remova caracteres da esquerda até que sua cópia anterior desapareça; em seguida, adicione-o e meça. Você descarta caracteres apenas quando necessário, então, para cada right, a janela é a sequência mais longa sem repetições que termina ali, e a melhor substring termina em algum ponto. Cada caractere entra no conjunto uma vez e sai no máximo uma vez: O(n).

Algoritmo

Comece com um conjunto vazio, left = 0 e best = 0.
Percorra cada índice com right.
Enquanto s[right] estiver no conjunto, remova s[left] e avance left uma posição.
Adicione s[right] ao conjunto.
Se right - left + 1 for maior que best, armazene esse valor.
Retorne best.

def lengthOfLongestSubstring(s):
    in_window = set()  # the characters between left and right
    left = 0
    best = 0
    for right in range(len(s)):
        # Shrink from the left until s[right] is no longer inside.
        while s[right] in in_window:
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best

Janela deslizante que salta para o índice visto pela última vez

Intuição

Você já sabe onde left deve chegar: uma posição após a cópia anterior do novo caractere. Armazene o último índice de cada caractere em um mapa ou em um array com uma posição por código de caractere, e left pula até lá em uma única etapa.

Faça o salto somente quando esse índice estiver em left ou depois dele. Uma cópia mais antiga já está fora da janela, e saltar até ela moveria left para trás. A janela em cada etapa é a mesma que a versão com conjunto cria, e cada caractere agora custa uma consulta, uma comparação e uma gravação.

Algoritmo

Crie um mapa vazio de caracteres para o último índice e defina left = 0 e best = 0.
Percorra right por todos os índices, lendo o caractere ch nessa posição.
Se ch foi visto pela última vez em left ou depois, defina left como esse índice mais um.
Registre right como o último índice de ch.
Se right - left + 1 for maior que best, armazene esse valor.
Retorne best.

def lengthOfLongestSubstring(s):
    last_seen = {}
    start = 0
    best = 0
    for i, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        if i - start + 1 > best:
            best = i - start + 1
    return best

Armadilhas e casos extremos

Recuar left. Em abba, o primeiro a, no índice 0, já está fora da janela quando você chega ao último a. Avançar para o índice 1 traz o segundo b de volta e resulta em 3 em vez de 2.
Contar a janela como right - left. As duas extremidades estão dentro dela, então some um.
Converter a string toda para minúsculas primeiro. a e A são caracteres diferentes aqui, então aA tem comprimento 2.
Medir apenas quando aparece uma repetição. Uma string sem repetições, como z, nunca aciona essa condição, e a resposta acaba sendo 0.

Perguntas frequentes3

Qual é a complexidade de tempo de Longest Substring Without Repeating Characters?

A janela deslizante é executada em tempo O(n), em que n é o comprimento da string: a borda direita lê cada caractere uma vez, e a borda esquerda só avança. O espaço extra é O(k), em que k é o número de caracteres diferentes que a string pode conter, 62 neste caso.

Você deve usar um mapa hash ou um array para os últimos índices?

Ambos têm tempo O(n). Com um conjunto pequeno e fixo de caracteres, como neste caso, um array indexado pelo código do caractere evita o hashing e é mais rápido.

Qual é a diferença entre uma substring e uma subsequência?

Uma substring é um bloco de caracteres que ficam lado a lado, como ode em coddycode. Uma subsequência pode pular caracteres, como cdy. Este problema pede uma substring, por isso uma janela com duas extremidades funciona.

def lengthOfLongestSubstring(s):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

s = "coddycode"

Saída Esperada

Longest Substring Without Repeating Characters

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada substring

Janela deslizante com um conjunto

Janela deslizante que salta para o índice visto pela última vez

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos