明らかに答えは単調なので、二分探索を適用できます。

判定問題は、長さ \(K\) で左から \(0\) になるように操作できるだけ操作したのち先頭 \(K\) 項が \(0\) か判定すればよいです。この操作の後、長さを変えることで任意の長さの区間をこの後に挿入できるためです。

計算量は、\(N=|S|\) として、\(O(N \log N)\) です。

実装例(PyPy3,113ms)