No.252

何文字置き換えれば目的の文字列になるかどうかはハミング距離で表される.

$i$ 文字目から4文字と good とのハミング距離 $g(i)$ と, $i$ 文字目から7文字と ‘problem` とのハミング距離 $p(i)$ を計算する.

$G(i) = \min_{k \leq i} g(k)$, $P(i) = \min_{k \geq i} p(i)$ とすると $G(i) + P(i+4)$ の最小値を求めればいい.

ただし, $i$ 文字目より前に problem が現れている場合, その problem の1文字を置き換えて problem ではない文字列にしておかなければいけない.

よって, $i$ 文字目より前の problem の出現頻度を $F(i)$ とすると, $G(i) + P(i+4) + F(i)$ の最小値を求めることになる.