Problem statement

https://binarysearch.com/problems/Minimum-Number-of-Flips-to-Have-Alternating-Values/

Solution

The trick is the following: we need to look at all windows of size n in string s + s. Then if we replace every second symbol if this string with its flip, what we need to find is the biggest and smallest sums in windows of size n: smallest for alternating start with 0 and biggest for start with 1.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        ans = n
        R = list(s + s)
        R[1::2] = [1-int(x) for x in R[1::2]]
        R[::2] = [int(x) for x in R[::2]]
        acc = [0] + list(accumulate(R))
        for i in range(n):
            t = acc[i + n] - acc[i]
            ans = min(ans, t, n - t)

        return ans