OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
==== Enunciado ====

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


==== Idea ====


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 [[algoritmos-oia/maxima-longitud-de-substring-palindromica|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, ..., 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.


==== Código ====

<code cpp 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;

</code>
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
