SRM396 Div2 500

問題

長さLの文字列を考えた時、もし0-indexedで、i番目の文字と(i+p)番目の文字が全部等しい場合、「周期pで周期的」という。AとCとGとTからなる文字列dnaが与えられる。maxPeriod以下の周期でこの文字列を周期的にする場合、最低何文字を入れ替える必要があるか。

考え方

周期pが1からmaxPeriodだった場合それぞれについて、最小の入れ替え個数を調べて、その最小値を返す。
もし、周期がpだった場合の最小入れ替え個数は、i文字目とi+p文字目とi+2*p文字目と...の文字の個数を調べて一番使われている文字にすべて置き換えれば、入れ替え個数は最小となるので、その個数の合計がその周期での最小入れ替え数になる。