Abba (OmegaUp)


Link al problemaAbba

Dificultad: Medio

Problema: Dada una cadena $S$, $1 ≤ |S| ≤ 1000000$, y una operación $reemplaza(a, b)$ que reemplaza todas las ocurrencias del caracter $a$ por $b$ en $S$. Encontrar el mínimo número de aplicaciones de ella para que $S$ se convierta en un palíndromo.

Solución: A primera instancia parece un problema relativamente sencillo y conocido (la distancia de edición), sin embargo a pesar de que ese algoritmo nos da una solución, no es la óptima siempre puesto que no toma en cuenta la operación $reemplaza$ definida previamente. Para resolver este problema es necesario representarlo de una manera totalmente distinta: usando un grafo en el que cada caracter es un nodo y la aplicación de la operación $reemplaza$ entre ellos forma una arista.

Tomemos la cadena trestristestigres para desarrollar un ejemplo. Para resolverlo, debemos ver que cada letra del lado izquierdo se debe cambiar por una del lado derecho o viceversa para que se forme un palíndromo. Comenzaremos con la t más a la izquierda y la s más a la derecha, mira la tabla:
Cadena Grafo resultante
     _               _
     trestristestigres
    
     __             __
     trestristestigres
    
 ___           ___
     trestristestigres
    
 ____         ____
     trestristestigres
    
 _____       _____
     trestristestigres
    
 ______     ______
     trestristestigres
    
 _______   _______
     trestristestigres
    
 ________ ________
     trestristestigres
    
Debemos notar que a pesar de que en este caso una única componente incluye todos los nodos, podría suceder que no fuera así, y que los nodos estuvieran repartidos en distintas componentes.

Ahora, gracias a la ayuda del grafo podemos ver más sencillamente las transiciones que debemos hacer para convertir nuestra cadena en palíndromo, sin embargo también podemos observar que hay bucles inútiles, que si bien nos llevarían a una solución esta no sería la óptima. Usando $reemplaza(i, t)$, $reemplaza(e, r)$, $reemplaza(r, t)$, $reemplaza(g, s)$ y $reemplaza(s, t)$ la cadena original trestristestigres se convierte en ttttttttttttttttt que es un palíndromo. Tenemos que eliminar los bucles, haciendo uso de algún algoritmo (por ejemplo el de Kruskal) para convertir nuestro grafo en un árbol, por ejemplo este:

Por último nos podemos dar cuenta que en realidad no es necesario hacer la transformación de grafo a un árbol, solo llevar un conteo de los nodos en cada componente, puesto que sabemos que para que un grafo de $N$ nodos sea un árbol debe tener exactamente $N-1$ aristas.

Complejidad: $O(N)$, $N$ es la longitud de la cadena $S$ (formar el grafo es $N/2$, buscar las componentes conexas es $N$).

No hay comentarios on "Abba (OmegaUp)"

Leave a Reply