最適な文字列がどういう形になっているか考えると、パターンの前後は$a...ab...b \ ...$と$... \ y...yz...z$のようになっているはずなので、$S$から$P$を除いた上でソートしたものを$S'$とし、$P$を$S'$のどこに挿入するのが最善か調べる。$P$を$S'$の$i$文字目に挿入したものと$S'$の$i+1$文字目に挿入したものを比較するとき、この比較は辞書順に関して下に凸になっているので、最小となる場所を二分探索で探せばよい。
