SRM321 Div2 1000

問題

ある機械があり、leftボタン、rightボタン、enterボタンがついている。
ある文字列が与えられたとき、その文字列の一番左にカーソルがある。enterボタンを押すと、カーソルのある文字を出力し、出力した文字の部分は空白' 'に置き換わる。
文字列の辞書順で小さい文字(a,b,c,...)から出力していきたいとき、最小ボタン押し回数を返す。

例として、「ba」が与えられたら、
[b]a -> b[a](移動) -> b[_](出力) -> [b]_(移動) -> [_]_(出力)
で4回で出力できる。

考え方

例えば、各文字の位置を頂点としたグラフを作ると、最短ハミルトン路を求めることになる。しかし、nが50もあり計算は無理。

まず、すべての文字を出力するので、s.length()回は必ずenterを押す。すると、残りは移動回数だけを考えればよい。

あるポジションにカーソルがあり、次に押したい文字の一番左側のポジションをleft[i]、一番右側のポジションをright[i]とすると、「今のポジション→left[i]→right[i]」と動く場合と「今のポジション→right[i]→left[i]」と動く場合が考えられる。
なので、この2つの動き方をdfsで探索して一番移動距離が少ない動き方を調べればいい。