きままにものづくり

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

SRM597Div1Easy

問題

サイズNの文字列AとBが与えられる。A内のある文字を選び、それを先頭に持ってくるという操作だけができる。AからBにするのに必要な操作数の最小値を求めよ。AからBにできない場合は-1を返す。

解法

AとBの後ろの要素を比較する。同じだった場合は、次の要素を比較し、違った場合は一致するまでAの要素を後ろ側から探索する。(文字数)-(一致した回数)が答えとなる。

計算量

O(N)

コード