TopCoder Open 2012 Round 1C Div1 Hard

問題

英小文字からなる文字列がある。
この文字列の任意の二文字を入れ替える操作を繰り返して、文字列を回文にしたい。

必要な操作の回数の最小値を求めよ。
不可能な場合は-1を返せ。

制約条件

文字列の長さ≦50
同じ文字は高々2つまでしか現れない。

方針

奇数の文字が2種類以上あったらアウト。
長さが偶数のときに奇数が奇数個、長さが奇数のときに奇数が偶数個あったらアウト。

その他の場合は必ず回文が作れる。
貪欲に先頭から見ていってよいらしい。

証明は大雑把に言うと以下のような感じ。
password[i]とpassword[n-i-1]に辺を張ると、
ループがいくつかからなるグラフができる。
このループが全部self loopなら終了で、長さnループはセルフループにするのにスワップが必ずn-1回必要。
で、貪欲に先頭から入れ替えていけば、一回ごとにループが一つ小さくなるので、貪欲法で正しい答えがでる。