Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Moving the first character to the end selects a cyclic rotation. Every rotation appears as a length-n window in s + s. For any such window, the required flips are its mismatches with one of the two alternating patterns. Sliding mismatch counts avoids recomputing a whole rotation.

Approach

Double the string. For each alternating pattern, count mismatches in the first original-length window and record its expected characters. Slide the window, subtracting the outgoing mismatch and adding the incoming one while continuing the alternating expectation. Track the least mismatch count across windows and both patterns. Absolute pattern parity may differ at a rotated start, but testing both patterns covers either starting bit. Return the smallest count; rotations themselves do not contribute to the flip total.

class Solution:
    def minFlips(self, s: str) -> int:
        w = len(s)
        s *= 2
        n = len(s)

        def solve(tar):
            curr = 0
            prev_tar = [0] * n

            for i in range(w):
                if s[i] != tar:
                    curr += 1
                prev_tar[i] = tar
                tar = '1' if tar == '0' else '0'

            res = curr
            for i in range(w, n):
                if s[i - w] != prev_tar[i - w]:
                    curr -= 1
                if s[i] != tar:
                    curr += 1
                res = min(res, curr)
                tar = '1' if tar == '0' else '0'

            return res

        return min(solve('0'), solve('1'))

Complexity analysis

Let n = s.length. Time: O(n) across the two alternating targets and all length-n cyclic windows. Auxiliary space: O(n) for the doubled string and stored target characters.