{"id":8467,"date":"2021-08-04T22:29:11","date_gmt":"2021-08-05T05:29:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8467"},"modified":"2021-08-04T22:30:31","modified_gmt":"2021-08-05T05:30:31","slug":"leetcode-1864-minimum-number-of-swaps-to-make-the-binary-string-alternating","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1864-minimum-number-of-swaps-to-make-the-binary-string-alternating\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating"},"content":{"rendered":"\n

Given a binary string s<\/code>, return the minimum<\/strong> number of character swaps to make it alternating<\/strong>, or <\/em>-1<\/code> if it is impossible.<\/em><\/p>\n\n\n\n

The string is called alternating<\/strong> if no two adjacent characters are equal. For example, the strings \"010\"<\/code> and \"1010\"<\/code> are alternating, while the string \"0100\"<\/code> is not.<\/p>\n\n\n\n

Any two characters may be swapped, even if they are not adjacent<\/strong>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> s = \"111000\"\nOutput:<\/strong> 1\nExplanation:<\/strong> Swap positions 1 and 4: \"111000\" -> \"101010\"\nThe string is now alternating.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"010\"\nOutput:<\/strong> 0\nExplanation:<\/strong> The string is already alternating, no swaps are needed.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s = \"1110\"\nOutput:<\/strong> -1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= s.length <= 1000<\/code><\/li>
  • s[i]<\/code> is either '0'<\/code> or '1'<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    Two passes, make the string starts with ‘0’ or ‘1’, count how many 0\/1 swaps needed. 0\/1 swaps must equal otherwise it’s impossible to swap.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minSwaps(string s) {    \n    auto count = [&](int m) {\n      vector swaps(2);\n      for (int i = 0; i < s.length(); ++i, m ^= 1)\n        if (s[i] - '0' != m)\n          ++swaps[s[i] - '0'];\n      return swaps[0] == swaps[1] ? swaps[0] : INT_MAX;\n    };\n    \n    int ans = min(count(0), count(1));\n    return ans != INT_MAX ? ans : -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible. The string is called alternating if no two adjacent characters are equal.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[712,88,4,290],"class_list":["post-8467","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-alternating","tag-greedy","tag-string","tag-swap","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8467","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=8467"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8467\/revisions"}],"predecessor-version":[{"id":8470,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8467\/revisions\/8470"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8467"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8467"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8467"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}