F. Timelines Converge – The Quantum Fold

Define the pattern of a (validly) folded strip to be the set of characters, in order, seen from above after all folds are made.

It is always possible to fold the strip in such a way that no two adjacent characters in the pattern are equal. If we fold in between every pair of equal characters, and don't fold in between every pair of distinct characters, we will achieve this.

Also, there is only one obtainable pattern that is alternating in this way. It is never possible to fold in between two adjacent different characters, because that can never be part of a valid folding, and if there exists a pair of adjacent equal characters that you don't fold in between, the pattern will not be alternating.

To achieve this folding we can consider a segment as a contiguous section of the pattern that has alternating symbols. We can fold each segment on top of each other and obtain the optimal string as the length of the longest alternating section. to keep track of this we can count the patterns that have 0's at the even indexes and 1's at the odd indexes as a positive offset on a variable and count the length of the pattern's that have 0's at the odd indexes and 1's at the even indexes as a negative offset. The difference between the maximum offset and the minimum offset will give us the longest alternating offset which will be the answer.

Complexity: $$$O(n)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    offset = 0
    mx = 0
    mn = 0
    for i in range(n):
        c = s[i]
        if (c=='1' and i%2) or (c == '0' and i%2 == 0):
            offset+=1
        else:
            offset-=1
        mn = min(offset,mn)
        mx = max(offset,mx)
    print(mx-mn)