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

约 9 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 百度
标签
字符串 数学 贪心
目录

题目描述

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

题意分析

两个等长字符串 s1、s2，都只含字符 x 和 y。每次操作可以选一个 s1 里的位置和一个 s2 里的位置，把这两个位置上的字符互换。注意交换必须跨串——不能在同一个串内部交换两个位置。求让两串完全相同所需的最少操作次数，做不到返回 -1。

「必须跨串交换」是本题的核心限制。它意味着一次操作会同时改变两个串各一个位置，而且被交换的两个字符位置可以任意选，不要求下标相同。

已经相等的位置不需要动——如果去动它，等于人为制造两个新的不匹配位置，只会变差。所以只需要盯着 s1[i] != s2[i] 的那些位置。

因为字符只有 x、y 两种，不匹配的位置只有两种形态：s1[i] = 'x' 且 s2[i] = 'y'（记作 xy 型），或者反过来（记作 yx 型）。整个问题的信息量被压缩成两个计数。

字符串长度可到 1000，规模上完全不构成压力，这也暗示考点不在复杂度而在推理：要能证明最优操作次数的公式。

边界：两串本来就相同（答案 0）、不匹配总数为奇数（无解）、xy 与 yx 都为奇数、只有一种类型的不匹配。

解法：统计错位对数

核心思路

先把问题化简：设不匹配位置中 xy 型有 xy 个、yx 型有 yx 个。因为交换可以在任意位置之间进行，位置的具体下标毫无意义，状态就是二元组 $(xy,\ yx)$，目标是把它变成 $(0, 0)$。

先看一次操作能消掉什么。取两个同为 xy 型的位置 i 和 j：s1[i]='x'、s2[i]='y'、s1[j]='x'、s2[j]='y'。把 s1[i] 与 s2[j] 交换，得到 s1[i]='y'、s2[j]='x'，此时位置 i 变成 s1[i]='y'、s2[i]='y' 匹配，位置 j 变成 s1[j]='x'、s2[j]='x' 也匹配。一次操作消掉两个 xy 型。同理一次操作能消掉两个 yx 型。

再看一个 xy 型配一个 yx 型能不能一次解决。位置 i 是 ('x','y')，位置 j 是 ('y','x')。任何一次跨串交换都无法同时修好这两个位置——交换 s1[i] 和 s2[j] 会把两个位置分别变成 ('x','y') 和 ('y','x') 的另一种排布，仍然不匹配。实际最优是两步：先把 s1[i] 与 s1[j]……不行，同串不能换；正确的两步是先用一次交换把 xy 型转成 yx 型（例如交换 s1[i] 与 s2[i]，位置 i 从 ('x','y') 变成 ('y','x')），此时变成两个 yx 型，再用一次操作同时消掉。所以一对异型需要 2 次。

于是不变量/结论清楚了：同型两两配对，每对 1 次操作；剩下的异型一对，需要 2 次操作。

可行性判断：每次操作要么消掉 2 个同型，要么把 1 个 xy 变成 1 个 yx（总数不变）。无论哪种，不匹配位置的总数 xy + yx 的奇偶性要么减 2、要么不变——奇偶性是不变量。要归零就必须一开始是偶数，否则永远无解。

最优次数公式：先把 xy 内部两两配掉，用 $\lfloor xy/2 \rfloor$ 次；yx 内部两两配掉，用 $\lfloor yx/2 \rfloor$ 次。此时剩下的要么都是 0，要么 xy 和 yx 各剩 1 个（因为总数是偶数，两者的奇偶性必然相同），后者再花 2 次。所以答案是

\[\lfloor xy/2 \rfloor + \lfloor yx/2 \rfloor + 2 \cdot (xy \bmod 2)\]

最后那一项用 xy % 2 还是 yx % 2 完全等价，因为总数为偶时两者奇偶性一致。

这个次数是下界也是可达值：每次操作至多让不匹配数减 2，所以次数不可能小于 $\lceil (xy+yx)/2 \rceil$；当 xy、yx 都是偶数时上式恰好等于这个下界，当两者都是奇数时下界是 $(xy+yx)/2$，而上式比它多 1，这多出来的 1 正是「异型对无法一步解决」所强制的代价。

解题步骤

  • 一趟遍历，跳过 s1[i] == s2[i] 的位置。跳过而不是计数，是因为匹配位置对答案没有任何贡献，动它们只会更差。
  • 不匹配时看 s1[i]：为 'x' 则 xy++，否则 yx++。只需要看一个串的字符，因为字符集只有两个值，s1[i] 确定后 s2[i] 必然是另一个。
  • 遍历结束先判 (xy + yx) % 2 == 1，是则返回 -1。这一步必须在计算公式之前——奇偶性是可行性的充要条件，不先拦住的话后面的整除会给出一个看似合理但完全错误的数字。
  • 返回 xy / 2 + yx / 2 + (xy % 2) * 2。前两项是同型内部配对，第三项是异型残余；整数除法在这里正是想要的向下取整，不需要额外处理。

以 s1 = "xx"、s2 = "yy" 走一遍。位置 0：'x' != 'y'，s1[0] 是 'x'，xy 变 1。位置 1：同理 xy 变 2。总数 2 是偶数。答案 2/2 + 0/2 + (2%2)*2 = 1 + 0 + 0 = 1。验证：交换 s1[0] 和 s2[1]，s1 变成 "yx"、s2 变成 "yx"，一步完成，正确。

再看 s1 = "xy"、s2 = "yx"。位置 0：s1[0]='x'，xy 变 1。位置 1：s1[1]='y'，yx 变 1。总数 2 是偶数。答案 1/2 + 1/2 + (1%2)*2 = 0 + 0 + 2 = 2。验证：先交换 s1[0] 和 s2[0]，s1 变成 "yy"、s2 变成 "xx"，此时两个位置都是 yx 型；再交换 s1[0] 和 s2[1]，s1 变成 "xy"、s2 变成 "xy"，两步完成。这里也能看出为什么异型对不能一步解决——第一步之后不匹配数并没有减少。

最后看无解情形 s1 = "xx"、s2 = "xy"。位置 0 匹配跳过，位置 1 是 ('x','y')，xy 变 1。总数 1 是奇数，返回 -1。确实无论怎么换，总有一个位置对不上。

代码实现

// 只统计两类错位数，先用奇偶性判无解，再套同型配对 + 异型残余的公式。
class Solution {
    public int minimumSwap(String s1, String s2) {
        int xy = 0;
        int yx = 0;
        for (int i = 0; i < s1.length(); i++) {
            char a = s1.charAt(i);
            char b = s2.charAt(i);
            if (a == b) {
                continue;
            }
            if (a == 'x') {
                xy++;
            } else {
                yx++;
            }
        }

        if ((xy + yx) % 2 == 1) {
            return -1;
        }

        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
}

// 只统计两类错位数，先用奇偶性判无解，再套同型配对 + 异型残余的公式。
func minimumSwap(s1 string, s2 string) int {
	xy := 0
	yx := 0
	for i := 0; i < len(s1); i++ {
		if s1[i] == s2[i] {
			continue
		}
		if s1[i] == 'x' {
			xy++
		} else {
			yx++
		}
	}

	if (xy+yx)%2 == 1 {
		return -1
	}

	return xy/2 + yx/2 + (xy%2)*2
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为字符串长度。只做一趟遍历，每个位置做一次字符比较和一次计数自增，之后是常数次算术运算，没有嵌套或回扫。
  • 空间复杂度：$O(1)$。只用了 xy、yx 两个计数器和一个循环下标，与输入规模无关。

关键点总结

  • 当操作可以作用在任意位置之间时，位置下标就是无关信息，状态应该压缩成「各类不匹配的计数」。这一步压缩把一个看似组合爆炸的搜索问题变成了两个整数的算术，是本题最大的思维跨度。
  • 只有两种字符时，不匹配的形态必然只有两类。字符集大小直接决定了状态维度，这个判断在很多字符串配对题里能直接套用。
  • 可行性判断要找操作下的不变量。本题的不变量是「不匹配总数的奇偶性」——每次操作只能让它减 2 或不变，所以奇数输入必然无解。面试时把这句证明说出来，比直接给 (xy+yx) % 2 的代码更有说服力。
  • 「同型配对便宜、异型配对贵」是这类题的通用结构：先贪心消耗便宜的配对，再用固定代价处理残余。要能说清楚为什么残余最多只有一对异型（因为总数为偶时 xy 与 yx 同奇偶）。
  • 面试视角：这题的代码只有十行，考察点全在推导上。面试官会追问三件事——为什么 xy % 2 和 yx % 2 等价、为什么异型对要 2 次而不是 1 次、为什么这个次数是最小的。提前把这三段准备好，比背公式重要得多。
  • 判无解必须放在算公式之前。可行性检查和最优化计算是两个独立阶段，混在一起会让整除悄悄吞掉非法输入。

易错点总结

  • 错误写法：漏掉 (xy + yx) % 2 == 1 的判断直接套公式 → s1 = "xx"、s2 = "xy" 时 xy = 1、yx = 0，算出 0 + 0 + 2 = 2，正确答案是 -1。
  • 错误写法：把奇偶判断写成 xy % 2 == 1 || yx % 2 == 1 就返回 -1 → s1 = "xy"、s2 = "yx" 时 xy = 1、yx = 1 都是奇数，被误判为无解返回 -1，正确答案是 2。
  • 错误写法：最后一项写成 (xy % 2) * 1，认为一对异型只需 1 次 → s1 = "xy"、s2 = "yx" 返回 1，但一次跨串交换无法同时修好两个异型位置，正确答案是 2。
  • 错误写法：最后一项写成 (xy % 2 + yx % 2) * 2，把两边的残余都算上 → 同一个用例返回 4，实际两个残余合起来只需 2 次。
  • 错误写法：答案写成 (xy + yx) / 2 这种「每次消两个」的粗暴估计 → s1 = "xy"、s2 = "yx" 返回 1，忽略了异型对的额外代价。
  • 错误写法：统计时不跳过匹配位置，把 s1[i] == s2[i] 也归到某一类 → s1 = "xx"、s2 = "xx" 时会累出非零计数，返回值大于 0，正确答案是 0。
  • 错误写法：只统计不匹配总数，不区分 xy 与 yx → s1 = "xx"、s2 = "yy" 和 s1 = "xy"、s2 = "yx" 都有两个错位，但答案分别是 1 和 2；只知道总数无法判断残余是否为异型对。
  • 错误写法：用 Math.ceil((xy + yx) / 2.0) 代替整数运算 → 浮点结果需要转型，且在 xy、yx 都是奇数时给出 $(xy+yx)/2$，比正确答案少 1。
  • 错误写法：先做 xy /= 2 再用 xy % 2 → 取模的对象已经被除法改过，xy = 3 时先变成 1 再取模得 1，看似巧合正确，但 xy = 5 时先变成 2 再取模得 0，残余的那一个被漏掉，答案偏小。

相似题目

题目 难度 考察点
859. 亲密字符串 简单 限定恰好一次同串内交换，需要额外处理「存在重复字符」
1202. 交换字符串中的元素 中等 交换关系由下标对给出，要用并查集划分可自由重排的连通块
1657. 确定两个字符串是否接近 中等 判定可达性而非最少次数，比较的是字符集与频次多重集
1013. 将数组分成和相等的三个部分 简单 同样先用整除性做可行性剪枝，再一趟扫描贪心切分