OIA-Wiki

Dada una string $s$ de longitud $n$, remover la menor cantidad de letras tal que la string que quede (con los caracteres en el orden inicial) sea un palíndromo.

Lo que pide el enunciado es la máxima subsecuencia palindrómica de la string. Una subsecuencia es exactamente eso, es una secuencia que se obtiene de seleccionar y dejar algunos índices de la secuencia inicial (o se puede ver como sacar los otros), en el orden inicial

Este problema a priori, como muchos de subsecuencias, parece ser muy difícil. Es que hay $2^n$ subsecuencias existentes (cada elemento puede estar o no, $2$ posibilidades).

Vamos a resolver el problema en $O(n^2)$.

¿Cómo? Programación dinámica!

Similar a la solución de programación dinámica para Máxima substring palindrómica, vamos a guardar en un $vector< vector<int> > tabla$, en la posición $j$ del vector $i$, $tabla[i][j]$, la longitud de la subsecuencia palindrómica más larga comenzando en la posición $i$ y terminando en la posición $j$ (inclusive) de la string.

Entonces, al principio tenemos $tabla[i][i]=1$. Y para longitud $2$, tenemos que $tabla[i][i+1]$ vale $2$ si $s[i]$ es igual a $s[i+1]$, y si no vale $1$. Ahora, supongamos que ya tenemos los valores de $tabla[i][i+k]$ para $k=0, 1, 2, \ldots, m$. Cómo calculamos los valores de $tabla[i][i+m+1]$?

Si $s[i]$ es igual a $s[i+m+1]$, entonces la subsecuencia más larga tendrá a estos caracteres como borde, y luego adentro se sumará la subsecuencia más larga, que está guardada en $tabla[i+1][i+m]$.

Y si los caracteres son distintos, sé que no voy a tener una subsecuencia con estos dos bordes. Entonces o me importa una subsecuencia que empiece en la posición $i$ y termine en $i+m$ (o antes, pero es lo mismo), o me importa la que empieza en $i+1$ y termina en $i+m+1$. Como estos dos segmentos tienen longitud $m$, por la hipótesis ya tenemos su información y estamos.

longest-palindromic-subsequence.cpp

// Dada una string s
int n=s.size();
vector< vector<int> > tabla(n, vector<int>(n, 0));
for(int i=0; i<n; i++){
    tabla[i][i]=1;
    if(i<n-1){
        if(s[i]==s[i+1]){
            tabla[i][i+1]=2;
        }else{
            tabla[i][i+1]=1;
        }
    }
}
 
for(int tam=3; tam<=n; tam++){
    for(int i=0; i<n-tam+1; i++){
        int j=i+tam-1;
        if(s[i]==s[j]){
            tabla[i][j]=tabla[i+1][j-1]+2;
        }else{
            tabla[i][j]=max(tabla[i][j-1], tabla[i+1][j]);
        }
    }
}
 
cout<<"La subsecuencia laindromica mas larga tiene longitud: "<<tabla[0][n-1]<<endl;