Long Inversions (Codeforces 1955E)
Tags: Greedy, 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: 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: 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.


Sample Inputs:
5
5
00100
5
01000
7
1011101
3
000
2
10

Sample Outputs:
3
2
4
3
1

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = input()
    ans = 0
    for i in range(n, 0, -1):
        z = -1
        for j in range(i):
            x = 0
            s1 = s[j::i]
            for k in s1:
                if k == '0':
                    x ^= 1
            if z != -1 and z != x:
                z = -2
                break
            z = x
        if z != -2:
            ans = i
            break
    print(ans)

Solution (Python):
def is_possible(lst, k):
    inverts = [False] * len(lst)
    inverted = False
    for i in range(len(lst) - k):
        if inverts[i]:
            inverted = not inverted
        v = lst[i]
        if inverted:
            v = not v
        if not v:
            inverts[i + k] = True
            inverted = not inverted
    zeroes = False
    ones = False
    for i in range(len(lst) - k, len(lst)):
        if inverts[i]:
            inverted = not inverted
        v = lst[i]
        if inverted:
            v = not v
        if v:
            ones = True
        else:
            zeroes = True
    return not (zeroes and ones)

def solve():
    n = int(input())
    lst = [True if x == '1' else False for x in input()]
    best = 0
    for i in range(1, n + 1):
        if is_possible(lst, i):
            best = i
    print(best)
test_cases = int(input())
for _ in range(test_cases):
    solve()

Solution (Python):
def check(x):
    v = s[:]
    res = 0
    for i in range(n - x + 1):
        res += v[i]
        if not res & 1:
            v[i] += 1
            v[i + x] -= 1
            res += 1
    for i in range(n - x + 1, n):
        res += v[i]
        if not res & 1:
            return False
    return True
for i in range(int(input())):
    n = int(input())
    s = list(map(int, input().strip()))
    for i in range(n - 1, 0, -1):
        s[i] -= s[i - 1]
    s.append(0)
    for i in range(n, -1, -1):
        if check(i):
            print(i)
            break