きままにものづくり

日々の気付いたことなんかを書いてます。

SRM589Div1Easy

問題

サイズNの文字列が与えられる。与えられた文字列を回文にするのに最小な時間を求めよ。
許される操作は、以下である。
任意の2つの文字A,Bを選択し。すべての文字AをBに変更する。この時、ひとつの文字を変更するのに1秒かかる。

解法

同じ文字と反対側にある文字をひとつのグループとし、その中で最多の文字に他の文字を変更する。

計算量

 O(N)

コード