Prefix Sum
IntuitionGiven a binary string s of length n, which consists of only 0 and 1, we may split s at any index i into two halves.  The second half is s[i:n], and the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Given a binary string `s` of length `n`, which consists of only `0` and `1`, we may split `s` at any index `i` into two halves.  The second half is `s[i:n]`, and the first half is `s[0:i]`.  We have to concatenate the second half and the first half and then flip some characters in the resulted array if necessary to make it an alternate binary array.

The complete search would not work, because an $O(n^2)$ of operations must be conducted (TLE).  We may use prefix sum to optimize the time complexity to $O(n)$.


# Approach
<!-- Describe your approach to solving the problem. -->
1. Construct two alternate binary arrays of length `n`: `s01` starts with `0`, and `s10` starts with `1`.
2. Compare `s` to `s01` and `s10`, respectively.  Count the number of mismatches.  Construct two arrays `ps01` and `ps10` that are prefix sums of the number of mismatches.  We adopt a 1-index convention here: the number of mismatches in substring `s[i:j]` is given by `ps[j] - ps[i]`.  **Number of mismatches is equivalent to the number of Type-2 operations we have to perform.**
3. Iterate through each valid index `i` from `0` to `n-1`.  At each index, consider two possibilities:
    (a) The second half is made into an alternate binary string starting with `0`.  The number of mismatches in the second half can be queried by prefix sums in $O(1)$.  Namely, if `i` is even, it is simply `ps01[n] - ps01[i]`.  In case `i` is odd, we have to query the `ps10` array by `ps10[n] - ps10[i]`.  This is because, in `ps10` we stored cummulative mismatches by assuming the entire array starts with `1`, and if `i` is odd, the target character would be `0` starting at index `i`.
        The first half continues from the end of the second half.  Depending on the parity of `n-i`, the number of characters in the second half, we query eitehr `ps01[i]` or `ps10[i]` to get the total number of mismatches.
        We then have a candidate answer.  Take the minimum between the current answer and this candidate answer.
    (b) An alternative is for the second half to start with `1`.  This mirrors the analysis and computations as in part (a).
4. Return the answer after part 3.


# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n)$

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(n)$

# Code
```python3 []
class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        s01 = '01' * (n//2) + '0' * int(n%2==1)
        s10 = '10' * (n//2) + '1' * int(n%2==1)
        ps01 = [0]
        ps10 = [0]
        for a, b in zip(s, s01): ps01.append(ps01[-1] + int(a!=b))
        for a, b in zip(s, s10): ps10.append(ps10[-1] + int(a!=b))
        ans = float('inf')
        for i in range(n):
            if i % 2 == 0:
                second01 = ps01[n] - ps01[i]
                if (n-i) % 2 == 0:
                    first01 = ps01[i]
                else:
                    first01 = ps10[i]
                ans = min(ans, first01 + second01)
                second10 = ps10[n] - ps10[i]
                if (n-i) % 2 == 0:
                    first10 = ps10[i]
                else:
                    first10 = ps01[i]
                ans = min(ans, first10 + second10)
            else:
                second01 = ps10[n] - ps10[i]
                if (n-i) % 2 == 0:
                    first01 = ps01[i]
                else:
                    first01 = ps10[i]
                ans = min(ans, first01 + second01)
                second10 = ps01[n] - ps01[i]
                if (n-i) % 2 == 0:
                    first10 = ps10[i]
                else:
                    first10 = ps01[i]
                ans = min(ans, first10 + second10)
        return ans

```
['Python3']