For prefix:
If s[i] == '0', prefix[i] = prefix[i-1].
If s[i] == '1', prefix[i] = min(prefix[i-1] + 1, i + 1).
For suffix:
If s[i] == '0', suffix[i] = suffix[i+1].
If s[i] == '1', suffix[i] = min(suffix[i+1] + 1, n - i).
The answer is min(prefix[i] + suffix[i+1]) for all i.
Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minimumTime(string s) {\n        int n = s.size();\n        vector<int> pre(n), suf(n);\n        pre[0] = s[0] == '1' ? 1 : 0;\n        for (int i = 1; i < n; ++i) {\n            if (s[i] == '1')\n                pre[i] = min(pre[i-1] + 1, i + 1);\n            else\n                pre[i] = pre[i-1];\n        }\n        suf[n-1] = s[n-1] == '1' ? 1 : 0;\n        for (int i = n-2; i >= 0; --i) {\n            if (s[i] == '1')\n                suf[i] = min(suf[i+1] + 1, n - i);\n            else\n                suf[i] = suf[i+1];\n        }\n        int ans = suf[0];\n        for (int i = 0; i < n-1; ++i)\n            ans = min(ans, pre[i] + suf[i+1]);\n        ans = min(ans, pre[n-1]);\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimumTime</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">string</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> s</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> s.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">size</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">();</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> pre</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(n), </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">suf</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(n);</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        pre[</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">] </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> s[</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\">0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">] </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">==</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> '1'</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> ?</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#D73A49;
Related Tags
