Long Inversions
Contest: Codeforces Round 938 (Div. 3)
Difficulty rating: 1700
Tags: brute force, greedy, implementation, sortings

A binary string $$$s$$$ of length $$$n$$$ is given. A binary string is a string consisting only of the characters '1' and '0'.

You can choose an integer $$$k$$$ ($$$1 \le k \le n$$$) and then apply the following operation any number of times: choose $$$k$$$ consecutive characters of the string and invert them, i.e., replace all '0' with '1' and vice versa.

Using these operations, you need to make all the characters in the string equal to '1'.

For example, if $$$n=5$$$, $$$s=00100$$$, you can choose $$$k=3$$$ and proceed as follows:

- choose the substring from the $$$1$$$-st to the $$$3$$$-rd character and obtain $$$s=\color{blue}{110}00$$$;
- choose the substring from the $$$3$$$-rd to the $$$5$$$-th character and obtain $$$s=11\color{blue}{111}$$$;

Find the maximum value of $$$k$$$ for which it is possible to make all the characters in the string equal to '1' using the described operations. Note that the number of operations required to achieve this is not important.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of the string $$$s$$$.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of the characters '1' and '0'.

It is guaranteed that the sum of the values $$$n^2$$$ over all test cases in the test does not exceed $$$25 \cdot 10^6$$$.

Output format:
For each test case, output the maximum integer $$$k$$$ ($$$1 \le k \le n$$$) for which it is possible to obtain a string $$$s$$$ consisting only of the characters '1' using the described operations.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
5
5
00100
5
01000
7
1011101
3
000
2
10

Example output:
3
2
4
3
1

Editorial:
No substring of the string needs to be inverted twice, as it does not change the string in any way. Let's fix $$$k$$$ and try to check if all the characters of the string can be made equal to 1. Suppose the first $$$i$$$ characters are already equal to 1, and $$$s_{i + 1}=0$$$. Then we need to invert all the bits starting from the $$$i + 1$$$-th to the $$$i + k$$$-th inclusive, i.e., not invert the first $$$i$$$ characters. If we invert any of the first $$$i$$$ characters, then we will have to invert it again. Either we will invert $$$s_{i + 1}$$$ again, so it will become equal to 0, or we will invert the characters to the left and come to the same situation, but for a smaller prefix.
Naive checking for a fixed $$$k$$$ takes $$$O(n \cdot k)$$$ time, if we honestly invert $$$k$$$ characters every time we encounter 0. We will maintain an inversion counter — how many times we need to invert a character of the string. Getting the actual value of a character is simple — if the counter is odd, invert the character. If $$$s_{i} = 0$$$, add $$$1$$$ to the counter, and remember that we need to subtract $$$1$$$ from the counter after position $$$i + k$$$, forming a segment $$$[i, i + k)$$$. This way, the complexity of the check will be $$$O(n)$$$.
It remains to iterate over $$$k$$$ and find the maximum for which it was possible to bring the string to all 1s. The complexity of the solution is $$$O(n ^ 2)$$$.