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:

     _               _
     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:

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