simulation + presum, O(n) time and O(n) space
Calculating the flips to make s to \'0101..\' is enough, marked as f(0). \nFlips to make a s to "1010.." will be len(s) - f(0).\nProof is simple:\nf(0) will get
Calculating the flips to make s to \'0101..\' is enough, marked as f(0). \nFlips to make a s to "1010.." will be len(s) - f(0).\nProof is simple:\nf(0) will get how many "0" and "1\'"in wrong place. but if we want to make s start with 1, f(0) will be those \'0\' and \'1\' that in correct place.\n\n**Presum**\nNow we only care about the target pattern "0101..".\npresum[i] means for first i chars, how many flips is needed.\n\n**Rotation**\nAfter rotation, ith char will be moved to head.\nThe flips needed in substring s[i:] will be r = presum[-1] - presum[i].\nThe value at position i will be i & 1.\nAnd then, the value at position 0 will be start = (i & 1) ^ ((n - i) & 1), because 0th char will be placed at the tail.\nThe substring on the left is s[:i].\nIf start == 0, flips on the left is l = presum[i].\nIf start == 1, flips on the left is l = i - presum[i].\n\nMinimum flips needed, if we rotate the string at i, is min(l + r, n - l - r)\n\n**Python**\n```python\nclass Solution:\n    def minFlips(self, s: str) -> int:\n        n = len(s)\n        presum = [0]\n        for i, c in enumerate(s):\n            presum.append(presum[-1] + (int(c) ^ (i & 1)))\n            \n        res = n\n        for i in range(n):\n            # make ith char be i & 1, 0th char will be (i & 1) ^ ((n - i) & 1)\n            r = presum[-1] - presum[i]\n            start = (i & 1) ^ ((n - i) & 1)\n            l = presum[i] if not start else i - presum[i]\n            res = min(res, l + r, (n - l - r))\n        return res\n```\n\n**Java**\n```\nclass Solution {\n    public int minFlips(String s) {\n        int n = s.length();\n        int[] presum = new int[n + 1];\n        for (int i = 0; i < n; i++) {\n            presum[i + 1] = presum[i] + ((s.charAt(i) - \'0\') ^ (i & 1));\n        }\n        \n        int res = n;\n        for (int i = 0; i < n; i++) {\n            int r = presum[n] - presum[i];\n            int start = (i & 1) ^ ((n - i) & 1);\n            int l = start == 0 ? presum[i] : i - presum[i];\n            res = Math.min(res, Math.min(l + r, n - l - r));\n        }\n        return res;\n    }\n}\n```
[]