交换字符使得字符串相同

难度: Medium

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

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

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

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

示例 1：

输入：s1 = "xx", s2 = "yy"
输出：1
解释：
交换 s1[0] 和 s2[1]，得到 s1 = "yx"，s2 = "yx"。

示例 2：

输入：s1 = "xy", s2 = "yx"
输出：2
解释：
交换 s1[0] 和 s2[0]，得到 s1 = "yy"，s2 = "xx" 。
交换 s1[0] 和 s2[1]，得到 s1 = "xy"，s2 = "xy" 。
注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx"，因为我们只能交换属于两个不同字符串的字符。

示例 3：

输入：s1 = "xx", s2 = "xy"
输出：-1

提示：

1 <= s1.length, s2.length <= 1000
s1.length == s2.length
s1, s2 只包含 'x' 或 'y'。

Submission

运行时间: 23 ms

内存: 16.0 MB

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy,yx=0,0
        for i in range(len(s1)):
            if s1[i]=='x' and s2[i]=='y':
                xy=xy+1
            if s1[i]=='y' and s2[i]=='x':
                yx=yx+1
        if (xy+yx)%2==1:
            return -1
        return xy//2+yx//2+xy%2+yx%2

Explain

此题解首先通过遍历字符串 s1 和 s2，统计两种不匹配情况的个数：s1中的'x'与s2中的'y'的不匹配个数(xy)，以及s1中的'y'与s2中的'x'的不匹配个数(yx)。接着，检查这两个计数（xy 和 yx）之和是否为奇数，如果是奇数，则无法通过交换使两字符串相同，因此返回-1。如果是偶数，则计算将这些不匹配通过最少交换次数解决所需要的交换次数。每两个 xy 或 yx 可以通过一次交换解决（即 xy//2 + yx//2 次），而每有一个单独的 xy 或 yx 将需要额外两次交换（这是因为单独的一个 xy 和一个 yx 可以组合成一次交换）。因此，总的交换次数为 xy//2 + yx//2 + xy%2 + yx%2。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        # 初始化两种不匹配的计数器
        xy, yx = 0, 0
        # 遍历字符串中的每个字符，计算不匹配情况
        for i in range(len(s1)):
            if s1[i] == 'x' and s2[i] == 'y':
                xy += 1  # s1为x，s2为y的情况
            if s1[i] == 'y' and s2[i] == 'x':
                yx += 1  # s1为y，s2为x的情况
        # 如果不匹配的总数为奇数，无法完全通过交换解决
        if (xy + yx) % 2 == 1:
            return -1
        # 计算最小交换次数
        return xy // 2 + yx // 2 + xy % 2 + yx % 2  # 每两个相同的不匹配可以一次解决，单独的需要两次交换

Explore

每次交换都涉及两个不匹配的字符，一个是xy类型，另一个是yx类型。如果不匹配的总数是奇数，这意味着至少有一个xy或yx无法找到对应的配对进行交换。因为每次有效的交换都必须处理一对不匹配（一个xy和一个yx），奇数个不匹配意味着至少有一个无法被配对，从而无法通过交换来完全匹配两个字符串。

这里的表述有误，正确的解释应该是：每两个相同类型的不匹配（要么是两个xy，要么是两个yx）可以通过一次交换解决。例如，如果有两个xy不匹配，即s1中的位置i和j都是'x'而s2中相应位置都是'y'，那么可以通过交换s2中的这两个位置的'y'来解决这两个不匹配。同理，对于两个yx不匹配也是相同的处理方式。

当有单独的xy和yx时，可以通过一次交换来解决这两个不匹配（交换一个xy位置的x与一个yx位置的y）。然而，如果有多余的单个xy或yx而另一个不足以配对，这种情况无法通过正常交换解决，因为每个有效的交换需要一个xy和一个yx。这样的情况会导致无法使两个字符串通过交换完全相同，这也是为什么检查(xy + yx)是否为奇数很重要的原因。

题解中的算法已经足够全面地处理了此问题的所有普通情况。它考虑了所有不匹配的可能性，并正确地计算了进行有效交换的最小次数。它还考虑了当不匹配的总数为奇数时，无法完成交换的情况。因此，算法已经涵盖了所有必要的逻辑来解决这个问题。