'''1247. 交换字符使得字符串相同

有两个长度相同的字符串 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
示例 4：

输入：s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
输出：4
'''
# 依次遍历比较同位置上的字符是否相同，且数量必须为偶数。因为若不相同的数量为奇数，则肯定不能交换成相同的字符串；
# 证明：
# 若[s1[i], s2[i]] == ["x", "y"]的个数为n1，[s1[i], s2[i]] == ["y", "x"]的个数为n2；所以字符'x'和'y'的个数都为n1+n2。

# 当n1+n2为奇数时，字符'x'和'y'无法分配到两个字符串中，则肯定无法交换成为两个相同的字符串。
# 当n1+n2为偶数时，则可以通过交换两个字符串的字符使得两个字符串完全相等
# 字符不相等分为两种情况讨论：

# 第一种
# s1 : "xy"
# s2 : "yx"
# 第二种
# s1 : "xx"
# s2 : "yy"
# 第一种需要交换两次才能都变成"xy"或"yx"。第二种则只需要交换一次即可。
# 因此在遍历时分别统计这两种情况的数量，最后再统一计算需要交换的次数。
class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        cnt1, cnt2 = 0, 0
        for i in range(len(s1)):
            if s1[i] == 'x' and s2[i] == 'y':
                cnt1 += 1
            elif s1[i] == 'y' and s2[i] == 'x':
                cnt2 += 1
        if (cnt1 + cnt2) % 2 != 0:
            return -1
        n1, m1 = divmod(cnt1, 2)
        n2, m2 = divmod(cnt2, 2)
        return n1 + n2 + 2 * m1
