Posted on

## 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
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