交换字符使得字符串相同 图解题解

两个只含 x、y 的串，最少换几次能逐位相同

s1 和 s2 等长、只由 x 和 y 组成。一次操作是从 s1 和 s2 里各挑一个位置，把这两个字符对调，不能在同一个串内部换。求最少多少次能让两串逐位完全一样，办不到就返回 −1。题面给了 s1="xx"、s2="yy" 换一次成，s1="xy"、s2="yx" 要两次。

真去模拟交换、搜最少步数，会卡在哪

真去枚举每一次跨串交换、拿 BFS 或回溯搜最短步数，交换组合随串长爆炸，状态多到跑不动。这题不用搜：两串对齐后，相同的位置压根不用碰，答案只由那些对不上的位置决定。

不匹配只有两种，怎么配对最省

把对不上的位置分两类：s1 是 x、s2 是 y 的记作 xy 类，反过来 s1 是 y、s2 是 x 的记作 yx 类。两个 xy 放一起，都是 s1 这头多个 x、s2 那头多个 y，把一处 s1 的 x 和另一处 s2 的 y 对调，两处当场同时对齐，一次搞定；两个 yx 同理。

麻烦的是落单的一个 xy 配一个 yx。它俩方向相反，对调任意两个字符都没法让两处同时对上——像 s1="xy"、s2="yx"，换一次只是把错位挪个地方。得先花一次把它变成两个同类，再花一次消掉，总共两次。于是每凑齐两个同类省一次，跨类一对认两次。

还有个前提：不匹配只能成对消掉。如果 xy 和 yx 加起来是奇数，最后必然剩一个配不出去，直接返回 −1。它等价于两串里 x 的总数为奇数。

数出两类，套成一个式子

扫一遍两串，用两个计数器 xy、yx 分别数两类不匹配。代码里 x 的编码比 y 小，s1 这位比 s2 这位小正好是 xy 类，反过来是 yx 类。先看 xy 加 yx 是不是奇数，是就返回 −1；否则 xy 类每两个记一次、共 xy//2 次，yx 类同理 yx//2 次，两类若各剩一个落单，跨类这一对再补两次，加起来就是答案。

xxyxyxxy 配 yxxyxxyx，数出 4 次

对齐后逐位看：第 0、3、6 位是 s1 为 x、s2 为 y，归 xy 类，xy=3；第 2、4、7 位是 s1 为 y、s2 为 x，归 yx 类，yx=3；第 1、5 位两串都是 x，跳过。不匹配共 6 个，偶数，有解。

xy 类 3 个，两个配一次、剩一个落单；yx 类 3 个也是一次加一个落单，累计两次。台面上剩一个 xy 和一个 yx，跨类这一对再花两次。1 加 1 加 2，得 4 次。再看无解的 s1="xx"、s2="xy"：第 0 位都是 x 跳过，第 1 位 s1 是 x、s2 是 y 记进 xy，xy=1、yx=0，总数 1 是奇数，返回 −1。

一遍扫描的开销，和几处一写就崩的坑

整个过程只是把两串对齐扫一遍、每位比一次记一次，末了几步常数运算，时间 O(n)；自始至终只有 xy、yx 两个计数器，空间 O(1)。忘了先判奇偶，无解的情形会被硬算出一个看着合理的数；把落单的 xy 配 yx 当成一次换掉，最终次数就少算一份；一上手就去搜索模拟，一道 O(n) 的题白白被做成指数级。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy = yx = 0
        for a, b in zip(s1, s2):
            xy += a < b
            yx += a > b
        if (xy + yx) % 2:
            return -1
        return xy // 2 + yx // 2 + xy % 2 + yx % 2

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.size(); ++i) {
            char a = s1[i], b = s2[i];
            xy += a < b;
            yx += a > b;
        }
        if ((xy + yx) % 2) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
};

Java

import java.util.*;
class Solution {
    public int minimumSwap(String s1, String s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.length(); ++i) {
            char a = s1.charAt(i), b = s2.charAt(i);
            if (a < b) {
                ++xy;
            }
            if (a > b) {
                ++yx;
            }
        }
        if ((xy + yx) % 2 == 1) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
}