Longest Palindromic Substring

+10

Recibes una cadena s de letras minúsculas del alfabeto inglés. Devuelve su subcadena palindrómica más larga: la secuencia más larga de letras consecutivas que se lee igual de izquierda a derecha que de derecha a izquierda. Si varias subcadenas tienen esa misma longitud máxima, devuelve la que empieza más a la izquierda.

Función

longestPalindrome(s: string) → string

sstring: la cadena en minúsculas que se va a buscar
Devuelvestring: la subcadena palindrómica más larga de s; la que aparece más a la izquierda si hay varias de igual longitud

Restricciones

1 ≤ s.length ≤ 2000
s contiene solo letras minúsculas del inglés.
Cuando varios palíndromos tienen la mayor longitud, la respuesta es el que tiene el índice inicial más pequeño.

Ejemplos

Entrada: s = "bananas"
Salida: "anana"
Explicación: "anana" se lee igual desde ambos extremos y tiene 5 letras. Ninguna secuencia más larga funciona: "banana" empieza con b y termina con a, "ananas" empieza con a y termina con s, y la palabra completa empieza con b y termina con s.

Entrada: s = "xyzzyabba"
Salida: "yzzy"
Explicación: "yzzy" y "abba" son palíndromos de longitud 4, y no existe ninguno más largo. "yzzy" comienza en el índice 1, antes que "abba" en el índice 5, así que gana el empate.

Entrada: s = "abcd"
Salida: "a"
Explicación: No hay dos letras iguales, así que todos los palíndromos son de una sola letra. El más a la izquierda es "a".

+18 pruebas ocultas al enviar

Para ir más allá

¿Puedes encontrar la respuesta en tiempo O(n)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un palíndromo se refleja alrededor de su centro, que puede ser una letra (longitud impar, como "anana") o el espacio entre dos letras iguales (longitud par, como "abba"). Comprobar cada subcadena por separado ignora esa estructura y cuesta O(n³). Expandir cada palíndromo hacia afuera desde su centro reutiliza cada comparación, lo que reduce la búsqueda a un tiempo O(n²) con O(1) de memoria adicional.

Comprueba cada subcadena

Correcto, pero no termina con las pruebas más grandes

Intuición

Una subcadena queda definida por su primer índice i y su último índice j. Compruébala con dos punteros: compara s[i] con s[j], después s[i+1] con s[j-1], y así sucesivamente, deteniéndote en la primera discrepancia. Si los punteros se encuentran o se cruzan sin que haya una discrepancia, la subcadena es un palíndromo. Conserva la más larga que encuentres.

Para la regla de desempate, recorre los inicios de izquierda a derecha y sustituye la mejor solo cuando un nuevo palíndromo es estrictamente más largo. Así, un palíndromo posterior de la misma longitud nunca desplaza a uno anterior, por lo que devuelves el que aparece más a la izquierda.

Esto examina las n(n+1)/2 subcadenas, así que no puede pasar por alto la respuesta. Es lento porque cada prueba puede recorrer la mitad de la subcadena. Para una cadena de 2000 copias de a, cada subcadena es un palíndromo y cada prueba llega hasta el medio: aproximadamente n³/12 ≈ 6.7 × 10^8 comparaciones de letras.

Algoritmo

Comienza con la mejor letra: inicio 0, longitud 1.
Para cada inicio i y cada final j ≥ i, compara las letras desde ambos extremos hacia el centro hasta que sean diferentes o los punteros se encuentren.
Si los punteros se encontraron sin que hubiera una discrepancia, s[i..j] es un palíndromo.
Si su longitud j-i+1 supera la mejor, registra i y esa longitud.
Devuelve la subcadena que empieza en el mejor inicio y tiene la mejor longitud.

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]

Tabla de palíndromos por longitud

Intuición

La fuerza bruta olvida lo que aprendió. Cuando prueba "anana", compara a con a y después n con n, y la segunda comparación es toda la prueba de "nan", que ya había ejecutado. La regla que ahorra trabajo: s[i..j] es un palíndromo cuando sus dos extremos coinciden y la parte entre ellos, s[i+1..j-1], es un palíndromo. Una comparación más una respuesta almacenada resuelven cada subcadena.

Almacena las respuestas en una tabla pal[i][j] y complétala por longitud. Cada letra individual es un palíndromo. Una subcadena de dos letras lo es cuando ambas letras coinciden. Para longitudes mayores, usa la regla: el interior tiene dos letras menos, así que su celda ya está completada.

En "bananas", pal[1][5] ("anana") es verdadero porque s[1] y s[5] son ambas a y pal[2][4] ("nan") es verdadero. Las longitudes aumentan y los comienzos avanzan de izquierda a derecha, así que el primer palíndromo de una nueva longitud récord también es el más a la izquierda de esa longitud. Aproximadamente n²/2 celdas cuestan O(1) cada una, así que el tiempo es O(n²); el precio es la memoria: 4 × 10^6 celdas para n = 2000.

Algoritmo

Crea una tabla de n × n llamada pal, con todos sus valores en false.
Para cada longitud de 1 a n y cada inicio i cuyo final j = i+length-1 quede dentro de la cadena, comprueba las dos letras de los extremos.
Marca pal[i][j] cuando coincidan y la longitud sea como máximo 2, o cuando pal[i+1][j-1] sea true.
Cuando la longitud de una celda marcada supere la mejor hasta el momento, registra i y la longitud.
Devuelve la subcadena que empieza en el mejor inicio.

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]

Expande alrededor de cada centro

Intuición

Todo palíndromo tiene un centro. Uno de longitud impar como "anana" tiene como centro una letra; uno de longitud par como "abba" tiene como centro el espacio entre sus dos letras centrales. Una cadena de longitud n tiene n letras y n-1 espacios, así que hay 2n-1 centros posibles.

Desde un centro, avanza hacia afuera una letra a cada lado mientras las dos letras coincidan. Cada paso demuestra que hay un palíndromo dos letras más largo. La primera discrepancia, o el borde de la cadena, pone fin al recorrido, y ningún palíndromo más largo puede compartir ese centro, porque contendría el par de letras que no coincide. Así que un recorrido hacia afuera encuentra el palíndromo más largo alrededor de cada centro, y el más largo de ellos es la respuesta.

En "bananas", empieza por la letra a en el índice 3. Las letras en las posiciones 2 y 4 son ambas n, las letras en las posiciones 1 y 5 son ambas a, y las letras en las posiciones 0 y 6 son b y s, así que el recorrido se detiene con una longitud de 5. El inicio es 3 - (5-1)/2 = 1, lo que da "anana". La misma fórmula, center - (length-1)/2 redondeada hacia abajo, también funciona para los centros en los espacios.

Recorre los centros de izquierda a derecha y reemplaza el mejor solo cuando la longitud sea estrictamente mayor. Dos palíndromos de igual longitud tienen la misma paridad, y el que tiene el centro más temprano empieza antes, así que gana el de más a la izquierda. El peor caso es una cadena formada por una sola letra repetida: cada centro avanza hasta el borde más cercano, alrededor de n²/2 = 2 × 10^6 pasos para n = 2000, y la memoria necesaria es de unos pocos enteros.

Algoritmo

Escribe expand(left, right): mientras ambos índices estén dentro de la cadena y las letras coincidan, decrementa left e incrementa right. Devuelve right-left-1.
Para cada centro desde 0 hasta n-1, toma el mayor valor entre expand(center, center) y expand(center, center+1).
Si esa longitud supera la mejor, establece el inicio óptimo en center - (length-1)/2, redondeado hacia abajo, y la mejor longitud en esa longitud.
Devuelve la subcadena en el inicio óptimo con la mejor longitud.

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]

Errores comunes y casos límite

La idea es breve, así que los errores se esconden en los detalles: los centros entre dos letras, la longitud después del recorrido, la regla para los empates y el recorte.

Expandir solo alrededor de las letras no detecta ningún palíndromo de longitud par. Con "abba", devuelve "a" en lugar de "abba".
El recorrido se detiene un paso más allá de cada extremo, así que el palíndromo es s[left+1..right-1] y su longitud es right-left-1. Usar right-left+1 añade dos letras que no coinciden.
Si se reemplaza el mejor resultado cuando las longitudes son iguales, se devuelve el palíndromo situado más a la derecha: "abba" en lugar de "yzzy" para "xyzzyabba".
Para un centro entre dos letras, center - length/2 queda una posición demasiado a la izquierda. En "xyzzyabba", el centro entre las letras después del índice 2 tiene longitud 4, y el inicio es 2 - (4-1)/2 = 1, no 0.
Las API de recorte varían: substr de C++ y Substring de C# reciben una longitud, mientras que substring de JavaScript y substring de Java reciben un índice final.
En la tabla, rellenar las filas empezando por 0 hace que se lea pal[i+1][j-1] antes de rellenarlo. Rellena por longitud o recorre los inicios desde el final.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la subcadena palindrómica más larga?

Expandirse alrededor de centros requiere un tiempo O(n²) y memoria adicional O(1). El enfoque de la tabla también requiere un tiempo O(n²), pero necesita memoria O(n²), y comprobar cada subcadena requiere un tiempo O(n³). El algoritmo de Manacher alcanza O(n), pero rara vez los entrevistadores lo esperan.

¿Por qué expandir desde el centro usa 2n-1 centros?

Un palíndromo de longitud impar tiene una letra central, y uno de longitud par tiene un espacio central entre dos letras iguales. Una cadena de n letras tiene n letras y n-1 espacios entre letras vecinas. Expandir solo desde las letras hace que se pasen por alto palíndromos como "abba".

¿Qué es el algoritmo de Manacher?

Encuentra el palíndromo más largo alrededor de cada centro en un tiempo total O(n). Mantiene el palíndromo que llega más lejos a la derecha hasta el momento, y un centro dentro de él parte de la respuesta de su centro reflejado, por lo que no se vuelve a comparar ninguna letra desde cero. Vale la pena conocerlo por su nombre; expandir alrededor del centro es la solución que suelen buscar los entrevistadores.

¿En qué se diferencia la subcadena palindrómica más larga de la subsecuencia palindrómica más larga?

Una subcadena es una secuencia de letras consecutivas, mientras que una subsecuencia puede omitir letras. En "character", la subcadena palindrómica más larga es "ara", pero "carac" es una subsecuencia palindrómica de longitud 5. La versión de subsecuencia se resuelve con una tabla sobre (i, j) que descarta un extremo cuando los dos extremos son distintos.

Python

def longestPalindrome(s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "bananas"

Esperado

"anana"

Longest Palindromic Substring

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba cada subcadena

Tabla de palíndromos por longitud

Expande alrededor de cada centro

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares