You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:


	Type-1: Remove the character at the start of the string s and append it to the end of the string.
	Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.


Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.


	For example, the strings "010" and "1010" are alternating, while the string "0100" is not.


&nbsp;
Example 1:

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".


Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating.


Example 3:

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 105
	s[i] is either '0' or '1'.


class Solution:
    def minFlips(self, s: str) -> int:
        prev = 0
        start_1, start_0, start_1_odd, start_0_odd = 0,0,sys.maxsize,sys.maxsize
        odd = len(s)%2
        for val in s:
            val = int(val)
            if val == prev:
                if odd:
                    start_0_odd = min(start_0_odd, start_1)
                    start_1_odd += 1
                start_1 += 1
            else:
                if odd:
                    start_1_odd = min(start_1_odd, start_0)
                    start_0_odd += 1
                start_0 += 1
            prev = 1 - prev
        return min([start_1, start_0, start_1_odd, start_0_odd])
class Solution {
    public int minFlips(String s) {
        /*
        * Sliding Window Approach
        */
        
        
        int n = s.length();
        
        int mininumFlip = Integer.MAX_VALUE;
        
        int misMatchCount = 0;
        for(int i = 0; i < (2 * n); i++){
            
            int r = i % n;
            
            //add mis watch count in current window
            if((s.charAt(r) - '0') != (i % 2 == 0 ? 1 : 0)) misMatchCount++;
            
            //remove mismatch count which are not relvent for current window
            if(i >= n && (s.charAt(r) - '0') != (r % 2 == 0 ? 1 : 0)) misMatchCount--;
            
            
            //misMatchCount : when valid binary string start from 1
            //n - misMatchCount : when valid binary string start from 0
            if(i >= n - 1) mininumFlip = Math.min(mininumFlip, Math.min(misMatchCount, n - misMatchCount));
        }
        
        return mininumFlip;
    }
}
class Solution {
public:
    int minFlips(string s)
    {
     int n = s.size();
     string ss = s+s;
     string s1, s2;
     int ans = INT_MAX;
     for(int i=0; i<ss.size(); i++)
     {
         s1+=(i%2?'1':'0');
         s2+=(i%2?'0':'1');
     }
     int ans1 = 0, ans2 = 0;
     for(int i=0; i<ss.size(); i++)
     {
         if(s1[i]!=ss[i]) ans1++;
         if(s2[i]!=ss[i]) ans2++;
         if(i>=n-1)
         {
             if(i!=n-1 && s1[i-n]!=ss[i-n]) ans1--;
             if(i!=n-1 && s2[i-n]!=ss[i-n]) ans2--;
             ans = min({ans,ans1,ans2});
         }
     }
     return ans;
    }
};
/**
 * @param {string} s
 * @return {number}
 */
var minFlips = function(s) {
    let length = s.length-1
    let flipMap = {
        '1': '0',
        '0': '1'
    }
    s = s + s
    let alt1 = '1'
    let alt2 = '0'
    let left = 0
    let right = 0
    let diff1 = 0
    let diff2 = 0
    let min = Infinity

    while (right < s.length) {
        if (right > 0) {
            alt1 = flipMap[alt1]
            alt2 = flipMap[alt2]
        }

        let current = s[right]
        if (current !== alt1) diff1++
        if (current !== alt2) diff2++
        if (right-left === length) {
            min = Math.min(diff1, diff2, min)
            if ((length+1)%2 === 0) {
                if (s[left] !== flipMap[alt1]) diff1--
                if (s[left] !== flipMap[alt2]) diff2--
            } else {
                if (s[left] !== alt1) diff1--
                if (s[left] !== alt2) diff2--
            }
            left++
        }
        right++
    }
    return min
};
Minimum Number of Flips to Make the Binary String Alternating