\(dp_{l,r}\) を与えられる文字列が \(S\) の \(l\) 文字目から \(r-1\) 文字目までからなる部分文字列であるときの本問題の答えとします。

\(dp_{0,|S|}\) の値を求めればよいので、区間 dp の要領で答えを求めていきます。最後に操作した箇所に注目して場合分けを行い、\(dp_{l,r}\) の計算を行います。

1. 一度も操作を行っていないとき

長さは \(r-l\) となっています。

2. 最後にした操作において、選択された o が \(l\) 文字目だったとき

f の位置を全探索します。\(i\) 文字目にあった f を用いて of を作る場合、\(l+ 1\) 文字目から \(i - 1\) 文字目までがすべて削除できていること、すなわち \(dp_{l+1,i} = 0\) が必要です。このとき、\(i + 1\) 文字目以降から最大 \(K\) 文字を削除できるので残る文字列の長さの最小値は \(\max(dp_{i+1,r} - K, 0)\) です。

3. 最後にした操作において、選択された o が \(l\) 文字目でなかったとき

\(i\) 文字目にあった o が選択されたとします。このとき、\(i\) 文字目は削除されていなかったことから、\(i\) 文字目より前と \(i\) 文字目以降を独立に考えてよいことがわかります。したがって、残る文字列の長さの最小値は \(dp_{l,i} + dp_{i,r}\) です。

よって、\(r-l > r'-l'\) を満たすすべての \((l', r')\) について \(dp_{l',r'}\) の値が求まっているとき、\(dp_{l,r}\) の値は時間計算量 \(O(r-l)\) で求めることができます。

以上より、全体として 時間計算量 \(O(|S|^3)\) で答えを求めることができました。