{"id":5801,"date":"2019-11-07T08:50:05","date_gmt":"2019-11-07T16:50:05","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5801"},"modified":"2019-11-08T08:25:38","modified_gmt":"2019-11-08T16:25:38","slug":"leetcode-1247-minimum-swaps-to-make-strings-equal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-1247-minimum-swaps-to-make-strings-equal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1247. Minimum Swaps to Make Strings Equal"},"content":{"rendered":"\n

You are given two strings s1<\/code> and s2<\/code> of equal length consisting of letters \"x\"<\/code> and \"y\"<\/code> only<\/strong>. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different<\/strong> strings, which means: swap s1[i]<\/code> and s2[j]<\/code>.<\/p>\n\n\n\n

Return the minimum number of swaps required to make s1<\/code> and s2<\/code> equal, or return -1<\/code> if it is impossible to do so.<\/p>\n\n\n\n

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

Input:<\/strong> s1 = \"xx\", s2 = \"yy\"\nOutput:<\/strong> 1\nExplanation: \n<\/strong>Swap s1[0] and s2[1], s1 = \"yx\", s2 = \"yx\".<\/pre>\n\n\n\n
Example 2: <\/strong><\/p>\n\n\n\n
Input:<\/strong> s1 = \"xy\", s2 = \"yx\"\nOutput:<\/strong> 2\nExplanation: \n<\/strong>Swap s1[0] and s2[0], s1 = \"yy\", s2 = \"xx\".\nSwap s1[0] and s2[1], s1 = \"xy\", s2 = \"xy\".\nNote that you can't swap s1[0] and s1[1] to make s1 equal to \"yx\", cause we can only swap chars in different strings.<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s1 = \"xx\", s2 = \"xy\"\nOutput:<\/strong> -1\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> s1 = \"xxyyxyxyxx\", s2 = \"xyyxyxxxyx\"\nOutput:<\/strong> 4\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= s1.length, s2.length <= 1000<\/code><\/li>
  • s1, s2<\/code> only contain 'x'<\/code> or 'y'<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Math<\/strong><\/h2>\n\n\n\n
    if s1[i] == s2[i] than no need to swap, so we can only look for
    case1. s1[i] = x, s2[i] = y, xy 
    case2. s1[i] = y, s2[i] = x, yx

    If case1 + case2 is odd, then there’s no solution.

    Otherwise we can use one swap to fix two xys (or two yxs)
    xx, yy => xy, yx

    One special case is there an extra xy and and extra yx, which takes two swaps
    xy, yx => yy, xx => xy, xy<\/p>\n\n\n\n
    Finally,
    ans = (case1 + 1) \/ 2 + (case2 + 1) \/ 2<\/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 minimumSwap(string s1, string s2) {        \n    int xy = 0;\n    int yx = 0;    \n    for (int i = 0; i < s1.length(); ++i) {\n      if (s1[i] == 'x' && s2[i] == 'y') ++xy;\n      if (s1[i] == 'y' && s2[i] == 'x') ++yx;\n    }\n    if ((xy + yx) % 2) return -1;\n    return (xy + 1) \/ 2 + (yx + 1) \/ 2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given two strings s1 and s2 of equal length consisting of letters “x” and “y” only. Your task is to make these two strings equal to each other. You can swap any two…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177,376],"class_list":["post-5801","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","tag-on","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5801","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=5801"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5801\/revisions"}],"predecessor-version":[{"id":5804,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5801\/revisions\/5804"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5801"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5801"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5801"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}