[LeetCode] 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 cannot 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

Constraints:

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

交换字符使得字符串相同。

有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 "x" 和 "y"，你需要通过「交换字符」的方式使这两个字符串相同。

每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。

交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。

最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心。因为需要让交换的次数尽可能小，那么相同位置上如果字母相同，就不需要做交换的操作了。我们需要处理的是那些相同位置上字母不一样的情形。

所以我们需要遍历一遍 s1 和 s2 两个字符串，看看不同字母有几处。记录的时候可以这样，我们需要四个变量，x1, y1 记录的是当 s1, s2 字母不同的时候， s1 里 x 和 y 的个数；x2, y2 记录的是当 s1, s2 字母不同的时候， s2 里 x 和 y 的个数。这里有一个 corner case，如果 x1 + x2 的和是奇数，那么一定无解，返回 -1。因为如果最后要使得两个字母相等，s1 中 x 的个数 +  s2 中 x 的个数一定是偶数。

一般的 case 有如下几种（只看 s1 即可），

xx - 需要去 s2 里找一个 y 来配对，组成 yx 或者 xy（取决于 s2 上相同位置是什么），一次操作即可

yy - 需要去 s2 里找一个 x 来配对，组成 yx 或者 xy（取决于 s2 上相同位置是什么），一次操作即可

xy - 同例子二，需要有两次操作。在写代码的时候，其实找到是 s1 中落单的 x

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minimumSwap(String s1, String s2) {
 3         int n = s1.length();
 4         int x1 = 0, y1 = 0;
 5         int x2 = 0, y2 = 0;
 6         for (int i = 0; i < n; i++) {
 7             char c1 = s1.charAt(i);
 8             char c2 = s2.charAt(i);
 9             if (c1 == c2) {
10                 continue;
11             }
12             if (c1 == 'x') {
13                 x1++;
14             } else {
15                 y1++;
16             }
17             if (c2 == 'x') {
18                 x2++;
19             } else {
20                 y2++;
21             }
22         }
23 
24         // corner case
25         // 不能配对的X的个数是奇数，说明一定无法配对，返回-1
26         if ((x1 + x2) % 2 == 1) {
27             return -1;
28         }
29 
30         // normal case
31         // Cases to do 1 swap:
32         // "xx" => x1 / 2 => how many pairs of 'x' we have ?
33         // "yy" => y1 / 2 => how many pairs of 'y' we have ?
34         // 
35         // Cases to do 2 swaps:
36         // "xy" or "yx" => x1 % 2
37         int swap = x1 / 2 + y1 / 2 + (x1 % 2) * 2;
38         return swap;
39     }
40 }

LeetCode 题目总结