O(N) / O(N) intuitive DP, prefix/suffix easy proof
The solution for any substring without any type 1 steps is the same as its reverse. Also, we can always apply all type 1\nbefore type 2 and get the same result.
The solution for any substring without any type 1 steps is the same as its reverse. Also, we can always apply all type 1\nbefore type 2 and get the same result. Applying a type 1 essentially rotates the string. So for `s.length == n`, we have `n` possible answers, one for each of `n` rotations. \n\nlet `pref0[i]` be the minimum cost to make `0..i` alternating if we set `s[0]` to `0`. \nlet `pref1[i]` be that if `s[0]` is set to 1.\n\nLikewise for `suff0[i]` and `suff1[i]` except we end with `0` and `1` respectively. \n\nThen the cost of rotating `s` by `k` or applying `k` type1 steps and then the necessary type 2 steps is \n`min(pref0[i] + suff1[i+1], pref1[i] + suff0[i+1])` because `s_rotated(k) = s[k...n-1] + s[0..k-1]` so the start of the prefix and the end of the suffix have to be opposite.\n\nWe can then just iterate over all rotations and take `O(1)` time to compute each of them, and select the maximum.\n\n```\n    vector<int> solve(string s, int start) {\n        int n = s.length();\n        vector<int> dp(n + 1, 0);\n        for (int i = 0; i < n; ++i) {\n            dp[i+1] = dp[i] + ((start + \'0\') == s[i]);\n            start = (start+1) % 2;\n        }\n        return dp;\n    }\n    \n    \n    int minFlips(string s) {\n        int n = s.length();\n        auto pref0 = slv(s, 0);\n        auto pref1 = slv(s, 1);\n        reverse(s.begin(), s.end());\n        auto suff0 = slv(s, 0);\n        auto suff1 = slv(s, 1);\n        reverse(suff0.begin(), suff0.end());\n        reverse(suff1.begin(), suff1.end());\n        int ans = INT_MAX;\n        for (int i = 0; i < n; ++i) {\n            ans = min(ans, min(pref0[i] + suff1[i], pref1[i] + suff0[i]));\n        }\n        return ans;\n        \n    }\n```
[]