JAVA DP O(N)
\nclass Solution {\n    public int minFlips(String s) {\n        int n = s.length();\n        int[][] f =  new int[n][2]; \n\t\t// f[i][0]: cost when starting a
```\nclass Solution {\n    public int minFlips(String s) {\n        int n = s.length();\n        int[][] f =  new int[n][2]; \n\t\t// f[i][0]: cost when starting as 0 at index 1 ending at index i\n\t\t// f[i][1]: cost when starting as 1 at index 0 ending at index i\n        for (int i = 0, val1 = 0, val2 = 1, res1 = 0, res2 = 0; i < n; i++, val1 ^= 1, val2 ^= 1) {\n            int val = s.charAt(i) - \'0\';\n            res1 += val ^ val1;\n            res2 += val ^ val2;\n            f[i][0] = res1;\n            f[i][1] = res2;\n        }\n        int[][] g =  new int[n][2];\n\t\t// g[i][0]: cost when starting as 0 at index n - 1 ending at index i\n\t\t// g[i][1]: cost when starting as 1 at index n - 1 ending at index i\n        for (int i = n - 1, val1 = 0, val2 = 1, res1 = 0, res2 = 0; i >= 0; i--, val1 ^= 1, val2 ^= 1) {\n            int val = s.charAt(i) - \'0\';\n            res1 += val ^ val1;\n            res2 += val ^ val2;\n            g[i][0] = res1;\n            g[i][1] = res2;\n        }\n        int res =  Math.min(g[0][1], g[0][0]);\n        for (int i = 1; i < n; i++) {\n\t\t    // g[i][1] + f[i - 1][0] denotes leftmost is 0 and rightmost is 1, split between index i -1 and i \n\t\t\t// g[i][0] + f[i - 1][1] denotes leftmost is 1 and rightmost is 0, split between index i -1 and i \n            res = Math.min(res, Math.min(g[i][1] + f[i - 1][0], g[i][0] + f[i - 1][1]));\n        }\n        return res;\n    }\n}\n```
[]