1247. Minimum Swaps to Make Strings Equal

1247. Minimum Swaps to Make Strings Equal (Medium)

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 characters that belong to different strings, which means: swap s1[i] and s2[j].

Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.

 

Example 1:

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: 
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2: 

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: 
Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note 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.

Example 3:

Input: s1 = "xx", s2 = "xy"
Output: -1

Example 4:

Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4

 

Constraints:

• 1 <= s1.length, s2.length <= 1000
• s1, s2 only contain 'x' or 'y'.

Related Topics:
String, Greedy

Similar Questions:

• Determine if Two Strings Are Close (Medium)

Solution 1.

a = "xxyyxyxyxx"
b = "xyyxyxxxyx"

First remove the places where a[i] == b[i]

a = "xyxyyx"
b = "yxyxxy"

We can first swap a[2] and b[0].

a = "xyyyyx"
b = "xxyxxy"
// Remove same characters
a = "yyyx"
b = "xxxy"

So we can see that for a pattern like the following, we just need one swap

a = "xx"
b = "yy"
// Or
a = "yy"
b = "xx"

So we whenever we see such pattern, we can increment the answer.

Let x and y be the count of x and y we see in a respectively, ignoring the places where a[i] == b[i].

When we see 'x' we increment x, otherwise, increment y.

When x == 2, we increment the answer and reset x to 0. The same for y.

In the end there are two cases:

• both x == 0 and y == 0, we return ans
• both x == 1 and y == 1, we return ans + 2
• x != y, we return -1

// OJ: https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minimumSwap(string a, string b) {
        int x = 0, y = 0, ans = 0;
        for (int i = 0; i < a.size(); ++i) {
            if (a[i] == b[i]) continue;
            if (a[i] == 'x') ++x;
            else ++y;
            if (x == 2) ++ans, x = 0;
            if (y == 2) ++ans, y = 0;
        }
        if (x != y) return -1;
        return x ? ans + 2 : ans;
    }
};