El desafío consiste en encontrar la longitud de la subsecuencia más larga dentro de una cadena s que cumpla con la propiedad de ser un palíndromo. A diferencia de un subsegmento contiguo, una subsecuencia se forma eliminando cero o más caracteres sin alterar el orden relativo de los caracteres restantes.

Por ejemplo, si la entrada es "bbbab", la longitud máxima es 4 (subsecuencia "bbbb"). Si la entrada es "cbbd", el resultado es 2 (subsecuencia "bb").

Enfoque Recursivo

Para resolver este problema, definimos una función recursiva que analice el intervalo [izq, der] de la cadena. La lógica se basa en tres reglas fundamentales:

1. Si izq == der, tenemos un solo carácter, por lo que la longitud es 1.
2. Si los caracteres en s[izq] y s[der] son idénticos, sumamos 2 a la longitud encontrada en el subrango interno [izq + 1, der - 1].
3. Si los caracteres son distintos, el resultado será el valor máximo entre omitir el carácter de la izquierda [izq + 1, der] o el de la derecha [izq, der - 1].

class Solucion:
    def longitud_lps(self, cadena: str) -> int:
        return self._resolver_recursivo(cadena, 0, len(cadena) - 1)

    def _resolver_recursivo(self, texto, inicio, fin):
        if inicio > fin:
            return 0
        if inicio == fin:
            return 1
        
        if texto[inicio] == texto[fin]:
            return 2 + self._resolver_recursivo(texto, inicio + 1, fin - 1)
        
        return max(
            self._resolver_recursivo(texto, inicio + 1, fin),
            self._resolver_recursivo(texto, inicio, fin - 1)
        )

Este método tiene una complejidad temporal exponencial de O(2^n) debido a la redundancia en los cálculos. Para optimizarlo, podemos implementar una técnica de optimización.

Optimización con Memoización

Utilizamos una estructura de datos (matriz o diccionario) para almacenar los resultados de los subproblemas ya resueltos, evitando llamadas recursivas innecesarias.

class Solucion:
    def longitud_lps(self, cadena: str) -> int:
        n = len(cadena)
        tabla_memo = [[-1] * n for _ in range(n)]
        return self._buscar_con_cache(cadena, 0, n - 1, tabla_memo)

    def _buscar_con_cache(self, texto, i, j, memo):
        if i > j: return 0
        if i == j: return 1
        if memo[i][j] != -1: return memo[i][j]
        
        if texto[i] == texto[j]:
            memo[i][j] = 2 + self._buscar_con_cache(texto, i + 1, j - 1, memo)
        else:
            memo[i][j] = max(
                self._buscar_con_cache(texto, i + 1, j, memo),
                self._buscar_con_cache(texto, i, j - 1, memo)
            )
        return memo[i][j]

Implementación con Programación Dinámica (Bottom-Up)

En lugar de recursión, utilizamos una matriz bidimensional dp donde dp[i][j] representa la longitud de la subsecuencia palindrómica más larga en el rango s[i...j]. Para llenar la tabla correctamente, debemos observar que cada celda depende de la fila inferior (i+1) y la columna anetrior (j-1), por lo que recorremos la cadena de atrás hacia adelante.

class Solucion:
    def longestPalindromeSubseq(self, s: str) -> int:
        longitud_total = len(s)
        # Inicializamos la matriz de estados
        matriz_dp = [[0] * longitud_total for _ in range(longitud_total)]
        
        # Iteramos desde el final hacia el principio para i
        for i in range(longitud_total - 1, -1, -1):
            # Cada carácter individual es un palíndromo de longitud 1
            matriz_dp[i][i] = 1
            
            # Evaluamos los subproblemas desde i + 1
            for j in range(i + 1, longitud_total):
                if s[i] == s[j]:
                    # Coincidencia: sumamos 2 al resultado del subproblema interno
                    matriz_dp[i][j] = matriz_dp[i + 1][j - 1] + 2
                else:
                    # Disparidad: tomamos el mejor resultado omitiendo un extremo
                    opcion_a = matriz_dp[i + 1][j]
                    opcion_b = matriz_dp[i][j - 1]
                    matriz_dp[i][j] = max(opcion_a, opcion_b)
                    
        return matriz_dp[0][longitud_total - 1]

Con este enfoque, la complejidad temporal se reduce a O(n²) y la complejidad espacial a O(n²), donde n es la longitud de la cadena de entrada. Esta solución es significativamente más eficiente para cadenas largas.