Algoritmos avanzados de palíndromos en Python

"Cuando lo simple deja de ser suficiente, es el momento de mirar más profundo y descubrir la belleza de lo complejo."

Detectar palíndromos es una tarea clásica en programación, pero cuando trabajamos con cadenas grandes, múltiples verificaciones o búsquedas de subcadenas, necesitamos aplicar algoritmos avanzados.

En esta guía veremos diferentes técnicas para resolver problemas complejos de palíndromos en Python, desde programación dinámica hasta algoritmos eficientes de búsqueda.

1. Búsqueda de subcadenas palíndromas más largas

El problema más común es encontrar la subcadena palíndroma más larga dentro de una cadena.

Solución básica con fuerza bruta (O(n³))

def subcadena_palindroma_mas_larga(s: str) -> str:
    n = len(s)
    max_pal = ""

    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            if sub == sub[::-1] and len(sub) > len(max_pal):
                max_pal = sub
    return max_pal

print(subcadena_palindroma_mas_larga("babad"))

Salida esperada:

"bab"  # o "aba"

2. Expansión desde el centro (O(n²))

Una forma más eficiente es expandir desde cada índice como centro, verificando palíndromos impares y pares.

def expandir_centro(s: str, izquierda: int, derecha: int) -> str:
    while izquierda >= 0 and derecha < len(s) and s[izquierda] == s[derecha]:
        izquierda -= 1
        derecha += 1
    return s[izquierda+1:derecha]

def subcadena_palindroma_mas_larga(s: str) -> str:
    max_pal = ""
    for i in range(len(s)):
        pal1 = expandir_centro(s, i, i)     # palíndromo impar
        pal2 = expandir_centro(s, i, i+1)   # palíndromo par
        max_pal = max([max_pal, pal1, pal2], key=len)
    return max_pal

print(subcadena_palindroma_mas_larga("cbbd"))

Salida esperada:

"bb"

3. Programación dinámica (O(n²))

La programación dinámica ayuda a verificar todas las subcadenas sin recalcular, almacenando resultados en una tabla booleana.

def palindromo_dp(s: str) -> str:
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    inicio, max_len = 0, 1

    for i in range(n):
        dp[i][i] = True  # palíndromo de un solo carácter

    for long in range(2, n+1):
        for i in range(n-long+1):
            j = i + long - 1
            if s[i] == s[j]:
                if long == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    if long > max_len:
                        inicio, max_len = i, long

    return s[inicio:inicio+max_len]

print(palindromo_dp("forgeeksskeegfor"))

Salida esperada:

"geeksskeeg"

4. Algoritmo de Manacher (O(n))

El algoritmo de Manacher es el más eficiente para este problema, permitiendo encontrar la subcadena palíndroma más larga en tiempo lineal.

def manacher(s: str) -> str:
    # Transformar la cadena para manejar palíndromos pares/impares
    T = "#" + "#".join(s) + "#"
    n = len(T)
    P = [0] * n
    centro = borde = 0

    for i in range(n):
        espejo = 2*centro - i
        if i < borde:
            P[i] = min(borde - i, P[espejo])

        # expandir alrededor del centro
        a, b = i + 1 + P[i], i - 1 - P[i]
        while a < n and b >= 0 and T[a] == T[b]:
            P[i] += 1
            a += 1
            b -= 1

        # actualizar centro y borde
        if i + P[i] > borde:
            centro, borde = i, i + P[i]

    # obtener el palíndromo más largo
    max_len, idx = max((n, i) for i, n in enumerate(P))
    inicio = (idx - max_len) // 2
    return s[inicio:inicio+max_len]

print(manacher("abacdfgdcaba"))

Salida esperada:

"aba"

Problemas comunes en algoritmos avanzados

  1. Manejo de índices → en algoritmos como Manacher, los errores de índice son frecuentes.
  2. Memoria en DP → las tablas 2D pueden ser pesadas para cadenas muy largas.
  3. Subcadenas pares e impares → siempre deben considerarse ambas.
  4. Caracteres especiales → normalizar la cadena antes de aplicar el algoritmo.

Retos avanzados

  • Encontrar todas las subcadenas palíndromas distintas de una cadena.
  • Implementar una versión recursiva con memoización.
  • Adaptar los algoritmos para trabajar con frases completas en lugar de palabras.

Los algoritmos avanzados de palíndromos en Python permiten resolver problemas más complejos de forma eficiente. Desde métodos básicos como expansión desde el centro hasta técnicas sofisticadas como Manacher, dominar estas estrategias abre la puerta a desafíos más grandes en programación competitiva, análisis de cadenas y algoritmos optimizados.

También te puede interesar: