Description

class Solution {
public:
    int minFlips(string s) {
        int n = s.length();
        s.insert(s.begin(), '2');
        
        vector<int> prediff0(n+1);
        vector<int> prediff1(n+1);
        prediff0[0] = prediff0[1] = 0;
        
        char zeroBeginCurrent = '0';
        for(int i = 1; i <= n; ++i) {
            // cout << zeroBeginCurrent << " ";
            if(s[i] == zeroBeginCurrent) {
                prediff0[i] = prediff0[i-1]; // begin with '0'
                prediff1[i] = prediff1[i-1] + 1;
            } else {
                prediff1[i] = prediff1[i-1];
                prediff0[i] = prediff0[i-1] + 1;
            }
            
            zeroBeginCurrent = 1 - (zeroBeginCurrent - '0') + '0';
            
        }
        
        int ret = INT_MAX / 2;
        // i: the position before the i-th as the pivot
        // start with the second half
        for(int i = 1; i <= n; ++i) {
            int m = n - i + 1; // number of elements in the second half
            
            if(i % 2 == 0) { // even
                if(m % 2 != 0) // odd
                    ret = ret = min(ret, min(prediff0[n], 
                                   prediff1[n]));
                else  // even
                    ret = min(ret, min(prediff0[n] - prediff0[i-1] + prediff1[i-1] - prediff1[0], 
                                   prediff1[n] - prediff1[i-1] + prediff0[i-1] - prediff0[0]));
            } else {
                if(m % 2 != 0) // odd
                    ret = min(ret, min(prediff0[n] - prediff0[i-1] + prediff1[i-1] - prediff1[0], 
                                   prediff1[n] - prediff1[i-1] + prediff0[i-1] - prediff0[0]));
                else  // even
                    ret = min(ret, min(prediff0[n], 
                                   prediff1[n]));
            }
            
        }
        
        return ret;
    }
};
// i = 4 n = 6, n - i + 1 = 3
//            i
// // 2 111 | 000
// 2 101 | 010
// prediff0: start with '0'
// prediff1: start with '1'
// traverse all the pivots