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

<ul>
	<li><strong>Type-1: Remove</strong> the character at the start of the string <code>s</code> and <strong>append</strong> it to the end of the string.</li>
	<li><strong>Type-2: Pick</strong> any character in <code>s</code> and <strong>flip</strong> its value, i.e., if its value is <code>&#39;0&#39;</code> it becomes <code>&#39;1&#39;</code> and vice-versa.</li>
</ul>

<p>Return <em>the <strong>minimum</strong> number of <strong>type-2</strong> operations you need to perform</em> <em>such that </em><code>s</code> <em>becomes <strong>alternating</strong>.</em></p>

<p>The string is called <strong>alternating</strong> if no two adjacent characters are equal.</p>

<ul>
	<li>For example, the strings <code>&quot;010&quot;</code> and <code>&quot;1010&quot;</code> are alternating, while the string <code>&quot;0100&quot;</code> is not.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;111000&quot;
<strong>Output:</strong> 2
<strong>Explanation</strong>: Use the first operation two times to make s = &quot;100011&quot;.
Then, use the second operation on the third and sixth elements to make s = &quot;10<u>1</u>01<u>0</u>&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;010&quot;
<strong>Output:</strong> 0
<strong>Explanation</strong>: The string is already alternating.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1110&quot;
<strong>Output:</strong> 1
<strong>Explanation</strong>: Use the second operation on the second element to make s = &quot;1<u>0</u>10&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def minFlips2(self, s: str) -> int:
        if len(s) == 1:
            return 0
        option1 = deque()
        option2 = deque()
        diff1 = 0
        diff2 = 0
        for i in range(len(s)):
            option1.append('0' if i % 2 == 0 else '1')
            option2.append('1' if i % 2 == 0 else '0')
            if option1[i] != s[i]:
                diff1 += 1
            if option2[i] != s[i]:
                diff2 += 1

        ds = deque(s)
        diff = min(diff1, diff2)
        for i in range(len(ds)):
            c = ds.popleft()
            ds.append(c)

            oc1 = option1.popleft()
            oc2 = option2.popleft()
            if c != oc1:
                diff1 -= 1
            if c != oc2:
                diff2 -= 1
            option1.append('0' if option1[-1] == '1' else '1')
            option2.append('0' if option2[-1] == '1' else '1')
            if c != option1[-1]:
                diff1 += 1
            if c != option2[-1]:
                diff2 += 1
            diff = min(diff, diff1, diff2)

        return diff

    def minFlips(self, s: str) -> int:
        
        def compute_diff_count(l1,l2):
            count = 0
            for i in range(len(l1)):
                if l1[i] != l2[i]:
                    count += 1
            return count
        
        n = len(s)
        ls = deque(s)
        lc1 = deque('0')
        lc2 = deque('1')
        for i in range(1,n):
            lc1.append('1' if lc1[-1] == '0' else '0')
            lc2.append('1' if lc2[-1] == '0' else '0')

        diff1 = compute_diff_count(ls, lc1)    
        diff2 = compute_diff_count(ls, lc2)
        min_diff = n
        for i in range(n):
            min_diff = min(min_diff,diff1,diff2)

            tmp_diff1 = diff1
            diff1 = diff2
            if ls[0] != lc2[0]:
                diff1 -= 1
            if ls[0] != lc1[-1]:
                diff1 += 1
            
            diff2 = tmp_diff1
            if ls[0] != lc1[0]:
                diff2 -= 1
            if ls[0] != lc2[-1]:
                diff2 += 1

            ls.append(ls.popleft())
        
        return min_diff
19200