\(S\) に含まれる o の数が \(K\) に等しいとき答えは \(S\) の ? をすべて . に置き換えたものです。以下、そうではない場合を考えます。

\(S\) の \(i\) 番目の文字が ? であるときを考えます。 \(i\) の左側の文字列について最大で \(M_1\) 文字、右側の文字列で最大で \(M_2\) 文字を o にできるとき、\(M_1 + M_2 \ge K\) であれば \(S\) の \(i\) 文字目は . にすることができます。

また、\(i\) の左側の文字列の右端を . にした上で最大で \(M'_1\) 文字、右側の文字列の左端を . にした上で最大で \(M'_2\) 文字を o にできるとき、\(M'_1 + M'_2 + 1 \ge K\) ならば \(S\) の \(i\) 文字目は o にすることができます。

ここで、\(dp_{i, j} =\) （\(S\) の \(i\) 文字目までの文字列について、先頭の文字が \(j=0\) ならば .、\(j=1\) ならば o である場合の、o の個数の最大値）とした動的計画法を \(S\) の左右から行うことで、上記の \(M_1, M_2, M'_1, M'_2\) をすべて計算可能なので、この問題を解くことができます。

実装例