No se si sepas utilizar arboles, la idea que se me ocurre es esta:
Generar un arbol que como raiz tenga la cadena entera, luego generar una rama por cada posibilidad, es decir, una nueva rama para sacar del lado derecho y otro nueva para el lado izquierdo e ir haciendo eso con cada rama nueva generada, al final que regrese el camino de la ruta con menos coste, te dejo una imagen con la idea:
http://s2.subirimagenes.com/privadas/previo/thump_2071344capturaarbol.png
Espero te guste la idea, me avisas
http://javatap1.blogspot.mx/
Generar un arbol que como raiz tenga la cadena entera, luego generar una rama por cada posibilidad, es decir, una nueva rama para sacar del lado derecho y otro nueva para el lado izquierdo e ir haciendo eso con cada rama nueva generada, al final que regrese el camino de la ruta con menos coste, te dejo una imagen con la idea:
http://s2.subirimagenes.com/privadas/previo/thump_2071344capturaarbol.png
Espero te guste la idea, me avisas
http://javatap1.blogspot.mx/