# 1247. Minimum Swaps to Make Strings Equal

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'`.

``````class Solution {
public:
int minimumSwap(string s1, string s2) {
int res = 0, n = s1.size(), cnt = 0;
unordered_map<string, int> m;
for (int i = 0; i < n; ++i) {
if (s1[i] == s2[i]) continue;
++m[string(1, s1[i]) + "_" + string(1, s2[i])];
}
for (auto &a : m) {
res += a.second / 2;
cnt += a.second % 2;
}
return cnt % 2 != 0 ? -1 : res + cnt;
}
};
``````

``````class Solution {
public:
int minimumSwap(string s1, string s2) {
int res = 0, n = s1.size(), xy = 0, yx = 0;
for (int i = 0; i < n; ++i) {
if (s1[i] == 'x' && s2[i] == 'y') ++xy;
else if (s1[i] == 'y' && s2[i] == 'x') ++yx;
}
return (xy % 2 != yx % 2) ? -1 : (xy / 2 + yx / 2 + (xy % 2) * 2);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1247

Determine if Two Strings Are Close

https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/

https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/discuss/419691/C%2B%2B-simple-solution

https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/discuss/419874/Simply-Simple-Python-Solution-with-detailed-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation