Clean Python 3, DP
To separate s into s1 + s2, if s1 starts with 1, s2 should ends with 0, and vice-versa\n\nTime: O(N)\nSpace: O(N)\n\nclass Solution:\n    def minFlips(self, s: 
To separate `s` into `s1` + `s2`, if `s1` starts with `1`, `s2` should ends with `0`, and vice-versa\n\nTime: `O(N)`\nSpace: `O(N)`\n```\nclass Solution:\n    def minFlips(self, s: str) -> int:\n        n = len(s)\n        dp_head = [[0] * (n + 1), [0] * (n + 1)]\n        dp_tail = [[0] * (n + 1), [0] * (n + 1)]\n        for i in range(2):\n            for j in range(n):\n                dp_head[i][j] = dp_head[i][j-1]\n                if ((j + 1) % 2) != (s[j] == str(i)):\n                    dp_head[i][j] += 1\n            for j in reversed(range(n)):\n                dp_tail[i][j] = dp_tail[i][j+1]\n                if ((n - j) % 2) != (s[j] == str(i)):\n                    dp_tail[i][j] += 1\n\n        ans = min(dp_head[0][n-1], dp_head[1][n-1])\n        for i in range(1, n):\n            zero_x_one = dp_head[0][i-1] + dp_tail[1][i]\n            one_x_zero = dp_head[1][i-1] + dp_tail[0][i]\n            ans = min(ans, zero_x_one, one_x_zero)\n        return ans\n```
[]