题目描述
思路解析
一句话答案：LeetCode 1247 交换字符使字符串相同：只数 s1 与 s2 不同处的 xy、yx 两类失配，同类两个一次换、跨类一对两次，总数为奇则无解返回 −1，时间 O(n)、空间 O(1)。
两个只含 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) 的题白白被做成指数级。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句话:不匹配分 xy、yx 两类,同类两两一次换掉,最后落单的一对 xy 和 yx 要两次。下面每帧都在套它。
总览 · 两串对齐,计数清零：上面这排是把 s1 和 s2 对齐后摆出来的 8 个位置,每个格子竖线左边是 s1 的字符、右边是 s2 的字符。准备两个计数器,xy 记「s1 是 x、s2 是 y」的位置数,yx 记「s1 是 y、s2 是 x」的位置数,现在都清成 0。从第 0 位开始,一位一位往右看。
看第 0 位：看第 0 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
第 0 位 · 归入 xy 类：这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 1。
看第 1 位：看第 1 位:s1 这位是 "x",s2 这位是 "x"。两个字符一样。
第 1 位 · 相同,跳过：这位 s1 和 s2 都是 "x",本来就一样,不用动它,标成蓝色跳过,计数都不变。
看第 2 位：看第 2 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
第 2 位 · 归入 yx 类：这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 1。
看第 3 位：看第 3 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
第 3 位 · 归入 xy 类：这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 2。
看第 4 位：看第 4 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
第 4 位 · 归入 yx 类：这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 2。
看第 5 位：看第 5 位:s1 这位是 "x",s2 这位是 "x"。两个字符一样。
第 5 位 · 相同,跳过：这位 s1 和 s2 都是 "x",本来就一样,不用动它,标成蓝色跳过,计数都不变。
看第 6 位：看第 6 位:s1 这位是 "x",s2 这位是 "y"。两个字符不一样,得分个类。
第 6 位 · 归入 xy 类：这位 s1 是 "x"、s2 是 "y",属于 xy 类,标成绿色,xy 计数加一,现在 xy = 3。
看第 7 位：看第 7 位:s1 这位是 "y",s2 这位是 "x"。两个字符不一样,得分个类。
第 7 位 · 归入 yx 类：这位 s1 是 "y"、s2 是 "x",属于 yx 类,标成红色,yx 计数加一,现在 yx = 3。
扫描完成 · 统计两类数量：8 个位置全看完:绿色 xy 类有 3 个(第 0、3、6 位),红色 yx 类有 3 个(第 2、4、7 位),蓝色相同位跳过 2 个。不匹配合计 6 个,是偶数,说明能配平、有解。下面开始配对算次数。
配对 · xy 类配出一对：先看绿色 xy 类。第 0 位和第 3 位都是「s1 是 x、s2 是 y」。把 s1 第 0 位的 "x" 和 s2 第 3 位的 "y" 对调一次,这两位就同时对齐了。两个同类不匹配,一次交换全消掉,已用 1 次。
配对 · xy 类剩一个单的：xy 类一共 3 个,两两配走一对,还剩第 6 位这一个 xy 落单,先放着,等会儿和落单的 yx 一起处理。
配对 · yx 类配出一对：再看红色 yx 类。第 2 位和第 4 位都是「s1 是 y、s2 是 x」,同样一次交换就能把这两位一起摆平,累计已用 2 次。
配对 · yx 类剩一个单的：yx 类也是 3 个,配走一对后剩第 7 位这一个 yx 落单。现在台面上剩一个 xy(第 6 位)和一个 yx(第 7 位)。
配对 · 跨类的一对要两次：落单这一个 xy 和一个 yx 不同类,不能一次解决。得先花一次交换把其中一个变成和另一个同类(比如把它俩先弄成两个 yx),再花一次消掉,这一对总共 2 次。加上前面两次,累计 4 次。
完成 · 答案 4 次：汇总:xy 类 3 个出 1 对、yx 类 3 个出 1 对,各 1 次;最后落单的 xy 加 yx 那一对 2 次。合起来 1 加 1 加 2 等于 4 次,跟开头说的答案对上了。
边界都一个套路:同类成对就一次,跨类落单一对就两次,不匹配总数为奇数直接 -1。
面试重点:同类一次、跨类两次的道理;奇数无解等价于 x 总数为奇;时间 O(n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，n 为字符串长度。两串对齐后每个位置只比一次、记一次,整体是一遍线性扫描,最后做几下常数运算
- 空间：O(1)，自始至终只用 xy 和 yx 两个整数计数器,没有额外的数组或栈,峰值占用是常数,跟串多长无关
易错点
面试追问把动画讲成自己的话
追问为什么两个同类不匹配一次交换就够,而一个 xy 加一个 yx 要两次?
追问什么时候返回 -1,背后的道理是什么?
追问这题的时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
用户分组
LeetCode 1282 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题