Subsecuencia y subcadena palindrómicas más largas
Aplique PD por intervalos para encontrar la subsecuencia palindrómica más larga y el truco de expansión alrededor del centro para hallar la subcadena palindrómica más larga.
Subsecuencia y subcadena palindrómicas más largas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Definiciones de palíndromos, revisadas
Una subsecuencia palindrómica es una subsecuencia (cuyos elementos no tienen que ser contiguos) que se lee igual de izquierda a derecha y de derecha a izquierda. Una subcadena palindrómica requiere caracteres contiguos. Para 'bbbab', la subsecuencia palindrómica más larga es 'bbbb' (longitud 4), mientras que la subcadena palindrómica más larga es 'bbb' (longitud 3). Estos dos problemas requieren técnicas diferentes a pesar de que sus nombres son similares.
Subsecuencia palindrómica más larga: estado de LPS
Defina dp[i][j] como la longitud de la subsecuencia palindrómica más larga en s[i..j]. La recurrencia es: si s[i] == s[j], entonces dp[i][j] = dp[i+1][j-1] + 2 (los dos caracteres coincidentes amplían el palíndromo interior). En caso contrario, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (se omite el carácter izquierdo o el derecho). Caso base: dp[i][i] = 1 para todos los caracteres individuales.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')Orden de llenado e implementación de LPS
Rellenamos la tabla de LPS con longitudes de intervalo crecientes, siguiendo el mismo patrón que la DP de intervalos general. Para cada intervalo [i, j] de longitud 2 o más, comprobamos si los dos caracteres de los extremos coinciden y aplicamos la recurrencia. La respuesta final es dp[0][n-1], la LPS de toda la cadena.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LPS mediante equivalencia con LCS
Una alternativa elegante: la LPS de la cadena s es igual a la LCS de s y su reverso s[::-1]. Esto se debe a que cualquier subsecuencia palindrómica de s es una subsecuencia común de s y de su reverso. Esta reducción permite reutilizar directamente su código de LCS. Para 'bbbab', el reverso es 'babbb' y su LCS tiene longitud 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4Subcadena palindrómica más larga: fuerza bruta
La subcadena palindrómica más larga requiere caracteres contiguos. Un enfoque de fuerza bruta comprueba todas las subcadenas O(n²) y verifica cada una en O(n) de tiempo, lo que da un total de O(n³). Existen dos enfoques más rápidos: DP de intervalos en O(n²) de tiempo y espacio y expansión desde el centro en O(n²) de tiempo pero O(1) de espacio. En las entrevistas, se prefiere la expansión desde el centro porque tiene una constante menor y un código más limpio.
DP de intervalos para subcadenas palindrómicas
Defina dp[i][j] = True si s[i..j] es un palíndromo. Recurrencia: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Casos base: dp[i][i] = True y dp[i][i+1] = (s[i] == s[i+1]). Registre la longitud máxima del palíndromo encontrado. Rellene la tabla siguiendo longitudes crecientes. Esto se ejecuta en O(n²) de tiempo y O(n²) de espacio.
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Técnica de expansión desde el centro
El enfoque de expansión desde el centro prueba cada carácter (y cada par de caracteres adyacentes) como posible centro de un palíndromo y se expande hacia fuera mientras ambos lados coincidan. Hay 2n-1 centros posibles (n de longitud impar y n-1 de longitud par). Cada expansión tarda como máximo O(n), lo que da un total de O(n²) con O(1) de espacio, una solución óptima para la mayoría de las entrevistas.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'Optimización de espacio de LPS
La DP de intervalos de LPS utiliza O(n²) de espacio. Cuando solo necesita la longitud (y no la subsecuencia real), puede reducir el espacio observando que dp[i][j] solo depende de dp[i+1][j-1], dp[i+1][j] y dp[i][j-1]. Al reutilizar filas y guardar un valor de la diagonal, puede conseguir O(n) de espacio, aunque la implementación es más compleja y rara vez se exige en las entrevistas.
Reconstrucción de la LPS
Para reconstruir la subsecuencia palindrómica real, recorra hacia atrás la tabla de DP. Empiece en (0, n-1). Si s[i] == s[j], añada ese carácter a ambos extremos del resultado y avance a (i+1, j-1). En caso contrario, avance a la posición con el valor mayor entre (i+1, j) y (i, j-1). Este recorrido codicioso hacia atrás recupera de forma única una subsecuencia palindrómica óptima.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')Comparación de la complejidad temporal de LPS y LCS
Tanto la LPS mediante DP de intervalos como la LCS se ejecutan en O(n²) de tiempo y O(n²) de espacio. La expansión desde el centro para la subcadena palindrómica más larga requiere O(n²) de tiempo, pero solo O(1) de espacio. El algoritmo de Manacher resuelve el problema de subcadenas en O(n) de tiempo y espacio, pero es lo bastante complejo como para que los entrevistadores rara vez lo esperen. En la mayoría de los contextos de entrevista, la expansión desde el centro es la solución óptima esperada para la variante de subcadenas.
Errores comunes y casos límite
Preste atención a estos errores: (1) confundir subsecuencia con subcadena — son problemas distintos con soluciones diferentes; (2) el caso base de DP de intervalos para intervalos de longitud 2 necesita un tratamiento especial, ya que dp[i+1][j-1] sería dp[i+1][i] (intervalo vacío); (3) para la expansión alrededor del centro, inicialice max_len = 1 (cada carácter individual es un palíndromo); y (4) al extraer el resultado, calcule start = i - (best-1)//2 para encontrar correctamente el índice inicial a partir del centro.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: LPS utiliza DP de intervalos con la recurrencia dp[i][j] = dp[i+1][j-1]+2 cuando los caracteres coinciden, la subcadena palindrómica más larga se resuelve mejor mediante la expansión alrededor del centro, en O(n²) de tiempo y O(1) de espacio, y LPS equivale a LCS de la cadena y su reversa. A continuación abordaremos Palindrome Partitioning II, que combina una tabla de palíndromos con DP unidimensional para encontrar el número mínimo de cortes.
Preguntas frecuentes
¿La lección «Subsecuencia y subcadena palindrómicas más largas» es gratis?
Sí — el texto completo de «Subsecuencia y subcadena palindrómicas más largas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Subsecuencia y subcadena palindrómicas más largas»?
Aplique PD por intervalos para encontrar la subsecuencia palindrómica más larga y el truco de expansión alrededor del centro para hallar la subcadena palindrómica más larga. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Subsecuencia y subcadena palindrómicas más largas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Patrón de PD por intervalos y orden de llenado
- Subsecuencia y subcadena palindrómicas más largas
- Palindrome Partitioning II
- Burst Balloons: PD por intervalos en sentido inverso