JZX轻语：简

LeetCode 1247 - 交换字符使得字符串相同

发表于2024年07月14日

#字符串 #贪心

需要一些观察和分析，首先，在同一个下标i下，如果s1[i]为x，而s2[i]为y，将其记为xy对；如果s1[i]为y，而s2[i]为x，将其记为yx对。那么，如果存在两个相同的xy对(或者两个相同的yx对)，那么可以通过一次交换将这两个对应的下标变为相同的字符；而如果仅有一个xy对以及一个yx对，那么需要两次交换才能将其变为相同的字符。对于整个字符串而言，如果xy对和yx对的个数总和为奇数，那么无法将其变为相同的字符串(不难证明，上述情况下，两个字符串的x个数为奇数，y个数，不可能能做到两个字符串相等)。如果为偶数，则存在可行解，且最优解可通过贪心的做法，尽量先同类对交换(只需要一次交换操作)(即xy对内部两两匹配，yx对内部两两匹配)，如果最后剩下一个xy对和一个yx对，那么需要两次交换。

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy_pair_cnt = yx_pair_cnt = 0
        for s1_ch, s2_ch in zip(s1, s2):
            if s1_ch != s2_ch:
                if s1_ch == 'x':
                    xy_pair_cnt += 1
                else:
                    yx_pair_cnt += 1
        if (xy_pair_cnt + yx_pair_cnt) % 2:
            return -1
        more, less = max(xy_pair_cnt, yx_pair_cnt), min(xy_pair_cnt, yx_pair_cnt)
        return more // 2 + less // 2 + more % 2 + less % 2

闪念标签：LC

题目链接：https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal/