[1] Solve the decision problem

Let \(M\) be the number of 1s in \(S\).

Consider for each \(i\ (1\le i \le N-K+1)\) whether we can make all of \(S_i,\ S_{i+1},\ \dots, S_{i+K-1}\) 1s and the others 0s. This can be done if and only if:

• the number of 1s in \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) is \(M\), and
• the number of 0s in \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) is \(0\).

Let us check this for each \(i\). If exactly one \(i\) satisfies these conditions, the answer is Yes; otherwise, it is No.

[2] Count 1s in \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) fast

If we naively count 1s in \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\), it will take \(\Theta(NK)\) time, which will run out of time for some test cases.

This can be improved by focusing on the change of the count in \(i\rightarrow i+1\). Specifically, the difference between the number of 1s in \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) and that in \(S_{i+1},\ S_{i+2},\ \dots,\ S_{i+K}\) only comes from \(S_i\) and \(S_{i+K}\). Thus, if the former is known, the latter can be found in \(O(1)\) time.

Therefore, the number of 1s in \(S_i,\ S_{i+1},\ \dots,\ S_{i+K-1}\) for every \(i\ (1\le i \le N-K+1)\) can be found in \(O(N)\) time in total.

The numbers of 0s can also be found similarly in \(O(N)\) time.

Using these counts, one can solve the decision problem in \(O(1)\) time, so the problem can be solved in \(O(N)\) time.