Longest Palindromic Substring

MédioDois ponteiros Programação dinâmica

+10

Você recebe uma string s composta por letras minúsculas do alfabeto inglês. Retorne sua substring palindrômica mais longa: a maior sequência de letras consecutivas que pode ser lida da mesma forma da esquerda para a direita e da direita para a esquerda. Se várias substrings tiverem esse mesmo comprimento máximo, retorne aquela que começa mais à esquerda.

Função

longestPalindrome(s: string) → string

sstring: a string em minúsculas a ser pesquisada
Retornastring: a substring palindrômica mais longa de s, a mais à esquerda em caso de empate

Restrições

1 ≤ s.length ≤ 2000
s contém apenas letras minúsculas do inglês.
Quando vários palíndromos tiverem o maior comprimento, a resposta será aquele com o menor índice inicial.

Exemplos

Entrada: s = "bananas"
Saída: "anana"
Explicação: "anana" é lido da mesma forma nos dois sentidos e tem 5 letras. Nenhum trecho maior funciona: "banana" começa com b e termina com a, "ananas" começa com a e termina com s, e a palavra inteira começa com b e termina com s.

Entrada: s = "xyzzyabba"
Saída: "yzzy"
Explicação: "yzzy" e "abba" são palíndromos de comprimento 4, e não existe nenhum maior. "yzzy" começa no índice 1, antes de "abba", no índice 5, então vence o empate.

Entrada: s = "abcd"
Saída: "a"
Explicação: Não há duas letras iguais, então todo palíndromo é uma única letra. A letra mais à esquerda é "a".

+18 testes ocultos ao enviar

Para ir além

Você consegue encontrar a resposta em tempo O(n)?

Dicas

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

0 de 3 abertas

Solução

Um palíndromo é simétrico em torno de seu centro, e esse centro é uma letra (comprimento ímpar, como "anana") ou o espaço entre duas letras iguais (comprimento par, como "abba"). Verificar cada substring separadamente ignora essa estrutura e custa O(n³). Expandir cada palíndromo a partir de seu centro reutiliza cada comparação, reduzindo a busca para O(n²) de tempo com O(1) de memória extra.

Verifique cada substring

Correta, mas não termina nos maiores testes

Intuição

Uma substring é determinada por seu primeiro índice i e seu último índice j. Teste-a com dois ponteiros: compare s[i] com s[j], depois s[i+1] com s[j-1] e assim por diante, parando na primeira divergência. Se os ponteiros se encontrarem ou se cruzarem sem que haja divergência, a substring é um palíndromo. Guarde a mais longa que encontrar.

Para seguir a regra de desempate, percorra os índices iniciais da esquerda para a direita e substitua a melhor opção somente quando um novo palíndromo for estritamente mais longo. Assim, um palíndromo posterior de mesmo comprimento nunca elimina um anterior, e você retorna o mais à esquerda.

Isso verifica todas as n(n+1)/2 substrings, então não pode deixar de encontrar a resposta. É lento porque cada teste pode percorrer metade da substring. Para uma string com 2000 cópias de a, toda substring é um palíndromo e cada teste vai até o meio: cerca de n³/12 ≈ 6.7 × 10^8 comparações de letras.

Algoritmo

Comece com a primeira letra como a melhor: início 0, comprimento 1.
Para cada início i e cada fim j ≥ i, compare as letras das duas extremidades em direção ao meio, até que sejam diferentes ou os ponteiros se encontrem.
Se os ponteiros se encontrarem sem divergência, s[i..j] é um palíndromo.
Se o comprimento j-i+1 for maior que o melhor, registre i e esse comprimento.
Retorne a substring no melhor início com o melhor comprimento.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

Tabela de palíndromos por comprimento

Intuição

A força bruta esquece o que aprendeu. Quando testa "anana", compara a com a e depois n com n, e a segunda comparação é o teste completo de "nan", que ela já executou. A regra que economiza trabalho: s[i..j] é um palíndromo quando suas duas extremidades coincidem e a parte entre elas, s[i+1..j-1], é um palíndromo. Uma comparação e uma resposta armazenada resolvem cada substring.

Armazene as respostas em uma tabela pal[i][j] e preencha-a por comprimento. Cada letra isolada é um palíndromo. Uma substring de duas letras é um palíndromo quando as duas letras coincidem. Para comprimentos maiores, use a regra: o interior tem duas letras a menos, então sua célula já está preenchida.

Em "bananas", pal[1][5] ("anana") é verdadeiro porque s[1] e s[5] são ambos a e pal[2][4] ("nan") é verdadeiro. Os comprimentos aumentam e os índices iniciais vão da esquerda para a direita, então o primeiro palíndromo de um novo comprimento recorde também é o mais à esquerda desse comprimento. Cerca de n²/2 células custam O(1) cada, então o tempo é O(n²); o preço é a memória: 4 × 10^6 células para n = 2000.

Algoritmo

Crie uma tabela pal n × n, toda com valores falsos.
Para cada comprimento de 1 a n e cada início i cujo fim j = i+length-1 permaneça dentro da string, verifique as duas letras das extremidades.
Marque pal[i][j] quando elas coincidirem e o comprimento for no máximo 2 ou pal[i+1][j-1] for verdadeiro.
Quando o comprimento de uma célula marcada superar o melhor, registre i e o comprimento.
Retorne a substring no melhor início.

def longestPalindrome(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways
    pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

Expanda ao redor de cada centro

Intuição

Todo palíndromo tem um centro. Um palíndromo de comprimento ímpar, como "anana", tem como centro uma letra; um de comprimento par, como "abba", tem como centro o espaço entre suas duas letras do meio. Uma string de comprimento n tem n letras e n-1 espaços, portanto 2n-1 centros possíveis.

A partir de um centro, avance para fora uma letra de cada lado enquanto as duas letras forem iguais. Cada passo comprova um palíndromo duas letras maior. A primeira divergência, ou a extremidade da string, encerra a busca, e nenhum palíndromo mais longo pode ter esse mesmo centro, pois conteria o par de letras divergentes. Assim, uma busca para fora encontra o maior palíndromo ao redor de cada centro, e o maior deles é a resposta.

Em "bananas", comece pela letra a no índice 3. As letras nos índices 2 e 4 são n, as letras nos índices 1 e 5 são a, e as letras nos índices 0 e 6 são b e s, então a busca para com comprimento 5. O início é 3 - (5-1)/2 = 1, o que resulta em "anana". A mesma fórmula, center - (length-1)/2 arredondada para baixo, também funciona para os centros entre letras.

Percorra os centros da esquerda para a direita e substitua o melhor resultado apenas quando encontrar um comprimento estritamente maior. Dois palíndromos de mesmo comprimento têm a mesma paridade, e aquele com o centro mais à esquerda começa primeiro, então o mais à esquerda vence. O pior caso é uma string formada por uma única letra repetida: cada centro avança até a borda mais próxima, cerca de n²/2 = 2 × 10^6 passos para n = 2000, e a memória usada é de alguns números inteiros.

Algoritmo

Escreva expand(left, right): enquanto os dois índices estiverem dentro da string e as letras corresponderem, diminua left e aumente right. Retorne right-left-1.
Para cada centro de 0 a n-1, escolha o maior valor entre expand(center, center) e expand(center, center+1).
Se esse comprimento superar o melhor, defina o melhor início como center - (length-1)/2, arredondado para baixo, e o melhor comprimento como esse valor.
Retorne a substring no melhor início com o melhor comprimento.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

Armadilhas e casos extremos

A ideia é simples, então os bugs se escondem nos detalhes: os centros entre letras, o comprimento após a expansão, a regra de desempate e o fatiamento.

Expandir apenas ao redor das letras deixa escapar todos os palíndromos de comprimento par. Para "abba", isso retorna "a" em vez de "abba".
A expansão para um passo depois de cada extremidade, então o palíndromo é s[left+1..right-1] e tem comprimento right-left-1. Usar right-left+1 adiciona duas letras que não correspondem.
Substituir o melhor palíndromo quando os comprimentos são iguais retorna o palíndromo mais à direita: "abba" em vez de "yzzy" para "xyzzyabba".
Para um centro entre letras, center - length/2 fica uma posição à esquerda demais. Em "xyzzyabba", o espaço após o índice 2 tem comprimento 4, e o início é 2 - (4-1)/2 = 1, não 0.
As APIs de fatiamento diferem: C++ substr e C# Substring recebem um comprimento, enquanto JavaScript substring e Java substring recebem um índice final.
Na tabela, preencher as linhas começando por 0 faz com que pal[i+1][j-1] seja lido antes de ser preenchido. Preencha por comprimento ou percorra os inícios de trás para a frente.

Perguntas frequentes4

Qual é a complexidade de tempo da maior substring palindrômica?

Expandir em torno dos centros leva O(n²) de tempo e O(1) de memória extra. A abordagem com tabela também leva O(n²) de tempo, mas precisa de O(n²) de memória, e verificar cada substring leva O(n³). O algoritmo de Manacher alcança O(n), mas raramente é esperado em entrevistas.

Por que expandir em torno do centro usa 2n-1 centros?

Um palíndromo de comprimento ímpar tem uma letra central, e um de comprimento par tem um espaço central entre duas letras iguais. Uma string de n letras tem n letras e n-1 espaços entre letras vizinhas. Expandir apenas a partir das letras não encontra palíndromos como "abba".

O que é o algoritmo de Manacher?

Ele encontra o maior palíndromo ao redor de cada centro em tempo total O(n). Mantém o palíndromo que alcançou mais à direita até o momento, e um centro dentro dele começa pela resposta do seu centro espelhado, para que nenhuma letra seja comparada novamente desde o início. Vale a pena conhecê-lo pelo nome; expandir ao redor do centro é a solução que os entrevistadores geralmente esperam.

Em que a substring palindrômica mais longa difere da subsequência palindrômica mais longa?

Uma substring é uma sequência de letras consecutivas, enquanto uma subsequência pode pular letras. Em "character", a maior substring palíndroma é "ara", mas "carac" é uma subsequência palíndroma de comprimento 5. A versão com subsequências é resolvida com uma tabela sobre (i, j) que descarta uma das extremidades quando as duas extremidades são diferentes.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "bananas"

Esperado

"anana"

Longest Palindromic Substring

Função

Restrições

Exemplos

Dicas

Solução

Verifique cada substring

Tabela de palíndromos por comprimento

Expanda ao redor de cada centro

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos