問題
サイズが50以下の文字列が与えられる。最初のK()文字と最後のK文字が同じになるように変化させた時の、変更箇所の最小値を求めよ。
解法
ふたつのパターンに分けて考える。Nは文字列のサイズとする。
の場合、最初のK文字と最後のK文字のdiffをとる。
それ以外の場合、オーバーラップしている箇所により単純にdiffをとるだけではダメになる。依存関係はN-Kの間隔となる。このことに注意して、依存関係にある文字の数と、その文字の最大出現回数を引くことで部分解が得られる。これをすべての依存グループで計算することで答えが求まる。topcoder wikiの解説を見ると、このアルゴリズムを拡張することで、の場合にも対応させている。
計算量
O(N)
N:与えられる文字列のサイズ
コード
※今回のコードはmapを用いているのでinsertのコストがかかる。intの配列を用いることで上の計算量となる