Min Flips for Alternating Binary String [Medium] — Circular Window

Problem Statement

You can rotate a binary string (move front char to back) and flip any char. Return minimum flips to make it alternating.

Input: "111000" → Output: 2
Input: "010"    → Output: 0

Intuition

The two target patterns are "010101..." and "101010...". Double the string (handles rotations). Slide a window of size n and count mismatches with each target pattern. Take the minimum.

Solutions

Python

def minFlips(s: str) -> int:
    n = len(s)
    s2 = s + s
    # Compare with "010101..." and "101010..."
    t1 = ''.join(str(i%2) for i in range(2*n))
    t2 = ''.join(str((i+1)%2) for i in range(2*n))
    diff1 = diff2 = 0
    # Initial window
    for i in range(n):
        if s2[i] != t1[i]: diff1 += 1
        if s2[i] != t2[i]: diff2 += 1
    ans = min(diff1, diff2)
    for i in range(n, 2*n):
        # Add right
        if s2[i] != t1[i]: diff1 += 1
        if s2[i] != t2[i]: diff2 += 1
        # Remove left
        if s2[i-n] != t1[i-n]: diff1 -= 1
        if s2[i-n] != t2[i-n]: diff2 -= 1
        ans = min(ans, diff1, diff2)
    return ans

C++

int minFlips(string s) {
    int n=s.size(); string ss=s+s;
    int d1=0,d2=0,ans=n;
    for(int i=0;i<2*n;i++){
        char t1='0'+i%2, t2='0'+(i+1)%2;
        if(ss[i]!=t1)d1++; if(ss[i]!=t2)d2++;
        if(i>=n){
            if(ss[i-n]!=('0'+(i-n)%2))d1--;
            if(ss[i-n]!=('0'+(i-n+1)%2))d2--;
            ans=min(ans,min(d1,d2));
        }
    }
    return ans;
}

Complexity

Time: O(n), Space: O(n)