{"id":8543,"date":"2021-08-09T18:49:44","date_gmt":"2021-08-10T01:49:44","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8543"},"modified":"2021-08-09T18:50:27","modified_gmt":"2021-08-10T01:50:27","slug":"leetcode-1888-minimum-number-of-flips-to-make-the-binary-string-alternating","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-1888-minimum-number-of-flips-to-make-the-binary-string-alternating\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1888. Minimum Number of Flips to Make the Binary String Alternating"},"content":{"rendered":"\n<p>You are given a binary string&nbsp;<code>s<\/code>. You are allowed to perform two types of operations on the string in any sequence:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Type-1: Remove<\/strong>&nbsp;the character at the start of the string&nbsp;<code>s<\/code>&nbsp;and&nbsp;<strong>append<\/strong>&nbsp;it to the end of the string.<\/li><li><strong>Type-2: Pick<\/strong>&nbsp;any character in&nbsp;<code>s<\/code>&nbsp;and&nbsp;<strong>flip<\/strong>&nbsp;its value, i.e., if its value is&nbsp;<code>'0'<\/code>&nbsp;it becomes&nbsp;<code>'1'<\/code>&nbsp;and vice-versa.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;number of&nbsp;<strong>type-2<\/strong>&nbsp;operations you need to perform<\/em>&nbsp;<em>such that&nbsp;<\/em><code>s<\/code>&nbsp;<em>becomes&nbsp;<strong>alternating<\/strong>.<\/em><\/p>\n\n\n\n<p>The string is called&nbsp;<strong>alternating<\/strong>&nbsp;if no two adjacent characters are equal.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the strings&nbsp;<code>\"010\"<\/code>&nbsp;and&nbsp;<code>\"1010\"<\/code>&nbsp;are alternating, while the string&nbsp;<code>\"0100\"<\/code>&nbsp;is not.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"111000\"\n<strong>Output:<\/strong> 2\n<strong>Explanation<\/strong>: Use the first operation two times to make s = \"100011\".\nThen, use the second operation on the third and sixth elements to make s = \"101010\".\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"010\"\n<strong>Output:<\/strong> 0\n<strong>Explanation<\/strong>: The string is already alternating.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> s = \"1110\"\n<strong>Output:<\/strong> 1\n<strong>Explanation<\/strong>: Use the second operation on the second element to make s = \"1010\".\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= s.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>s[i]<\/code>&nbsp;is either&nbsp;<code>'0'<\/code>&nbsp;or&nbsp;<code>'1'<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sliding Window<\/strong><\/h2>\n\n\n\n<p>Trying all possible rotations will take O(n<sup>2<\/sup>) that leads to TLE, we have to do better.<\/p>\n\n\n\n<p>concatenate the s to itself, then using a sliding window length of n to check how many count needed to make the string in the window alternating which will cover all possible rotations. We can update the count in O(1) when moving to the next window.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minFlips(string s) {\n    const int n = s.length();    \n    int ans = INT_MAX;\n    for (int i = 0, c0 = 0, c1 = 1, a0 = 0, a1 = 0; i < 2 * n; ++i, c0 ^= 1, c1 ^= 1) {\n      if (s[i % n] - '0' != c0) ++a0;\n      if (s[i % n] - '0' != c1) ++a1;\n      if (i < n - 1) continue;\n      if (i >= n) {\n        if (s[i - n] - '0' != c0 ^ (n & 1)) --a0;\n        if (s[i - n] - '0' != c1 ^ (n & 1)) --a1;\n      }\n      ans = min({ans, a0, a1});      \n    }    \n    return ans;\n  }\n};\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a binary string&nbsp;s. You are allowed to perform two types of operations on the string in any sequence: Type-1: Remove&nbsp;the character at&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[177,215,4],"class_list":["post-8543","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-medium","tag-sliding-window","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8543","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8543"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8543\/revisions"}],"predecessor-version":[{"id":8545,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8543\/revisions\/8545"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8543"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8543"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8543"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}