Notelock

Let the positions of the 1s be

$p_1 < p_2 < \dots < p_m.$

If there are no 1s, the answer is obviously $0$, because Teto has nothing to change.

Now focus on some 1 at position $i$. Teto can change it to 0 exactly when there is no 1 in the previous $k-1$ positions. In other words, it is vulnerable if the nearest earlier remaining 1 is at distance at least $k$, or does not exist.

The key detail: the scan goes left to right. So a protected 1 can act like a blocker for later 1s. If a later 1 is within distance $k-1$, then Teto sees that earlier 1 and cannot change the later one.

So the string breaks into chains of 1s:

• If two consecutive 1s are less than $k$ apart, they belong to the same chain.
• If the gap is at least $k$, the later 1 starts a new chain, because nothing before it can block it.

For each chain, we must protect at least one position. Specifically, the first 1 of the chain must be protected, because there is no earlier 1 close enough to save it. If we do not protect it, Teto can immediately delete it. Brutal, but fair.

Protecting the first 1 of a chain is also sufficient. Then the next 1 in the chain has a previous 1 within the last $k-1$ positions, so it cannot be changed. The next one is blocked by some earlier 1, and so on. By induction, every 1 in the chain stays unchanged.

Therefore the answer is simply:

Count every 1 whose previous 1 is either missing or at distance at least $k$.

That is the first 1 of each chain.

Algorithm:

1. Keep last, the index of the previous 1.
2. Scan the string left to right.
3. When we see a 1:
   • if there was no previous 1, or i - last >= k, this starts a new chain, so increment the answer;
   • update last = i.

The update always happens because every 1 can help block later 1s once the chain’s first 1 is protected.

Complexity is $O(n)$ per test case, which is tiny here.