[Java] O(n) Dynamic Programming
Dynamic programming, \nlet l[i][j] is the minimum number of type 2 operation to make substring (0, i) alternating with s[i] == j (0 <= j <= 1)\nlet [i][j] is th
Dynamic programming, \nlet l[i][j] is the minimum number of type 2 operation to make substring (0, i) alternating with s[i] == j (0 <= j <= 1)\nlet [i][j] is the minimum number of type 2 operation to make substring (i, s.length() - 1) alternating with s[i] == j (0 <= j <= 1)  \n\nthen for each i (1 -> s.length()) ans = Math.min(ans, l[i - 1][0] + r[i][1]). See the code for more details.\n\n```\nclass Solution {\n    public int minFlips(String s) {\n        \n        int n = s.length();\n        int[][] l = new int[n][2];\n        \n        int ans = 0;\n        \n        l[0][0] = (s.charAt(0) == \'0\') ? 0 : 1;\n        l[0][1] = (s.charAt(0) == \'1\') ? 0 : 1;\n        for(int i=1; i<s.length(); i++) {\n            l[i][0] = ((s.charAt(i) == \'0\') ? 0 : 1) + l[i - 1][1];\n            l[i][1] = ((s.charAt(i) == \'1\') ? 0 : 1) + l[i - 1][0];\n        }\n        \n        int[][] r = new int[n][2];\n        r[n - 1][0] = (s.charAt(n - 1) == \'0\') ? 0 : 1;\n        r[n - 1][1] = (s.charAt(n - 1) == \'1\') ? 0 : 1;\n        for(int i=n - 2; i>=0; i--) {\n            r[i][0] = ((s.charAt(i) == \'0\') ? 0 : 1) + r[i + 1][1];\n            r[i][1] = ((s.charAt(i) == \'1\') ? 0 : 1) + r[i + 1][0];\n        }\n        \n        ans = Math.min(l[n - 1][0], l[n - 1][1]);\n        for(int i=1; i<n; i++) {\n            if ((n - i) % 2 == 0) {\n                // 0101 0101 ? 1010 1010\n                ans = Math.min(ans, r[i][0] + ((i % 2 == 0) ? l[i - 1][1] : l[i - 1][0]));\n                ans = Math.min(ans, r[i][1] + ((i % 2 == 0) ? l[i - 1][0] : l[i - 1][1]));\n            } else {\n                // 101 0101\n                ans = Math.min(ans, r[i][0] + ((i % 2 == 0) ? l[i - 1][0] : l[i - 1][1]));\n                ans = Math.min(ans, r[i][1] + ((i % 2 == 0) ? l[i - 1][1] : l[i - 1][0]));\n            } \n        }\n        \n        return ans;\n    }\n}\n```
[]