What is the main pattern in the Minimum Swaps to Make Strings Equal problem?

The main pattern is greedy choice plus invariant validation, focusing on minimizing swaps by first ensuring mismatched positions are handled correctly.

How can I optimize this problem for larger input sizes?

The solution should already be optimized to O(n) time complexity, but focus on ensuring that the solution scales well by handling the swap logic efficiently.

What if the two strings have unequal counts of 'x' and 'y'?

If the counts of 'x' and 'y' in both strings are not equal, the problem is unsolvable, and you should return -1.

How do I handle edge cases where the strings are already equal?

In such cases, you simply return 0, as no swaps are needed to make the strings equal.

Can the logic for this problem be extended to other characters beyond 'x' and 'y'?

Yes, the greedy approach can be generalized to work with other characters, but you need to adjust the mismatch pair counting logic accordingly.

#1247

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

交换字符使得字符串相同

有两个长度相同的字符串 s1 和 s2 ，且它们其中只含有字符 "x" 和 "y" ，你需要通过「交换字符」的方式使这两个字符串相同。每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换…

数学字符串贪心

题目描述

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

提示：

1 <= s1.length, s2.length <= 1000
s1.length == s2.length
s1, s2 只包含 'x' 或 'y'。

lightbulb

解题思路

方法一：贪心

根据题目描述，两个字符串 $s_1$ 和 $s_2$ 都只包含字符 $x$ 和 $y$ ，且长度相同，因此可以将 $s_1$ 和 $s_2$ 中的字符一一对应起来，即 $s_1[i]$ 和 $s_2[i]$ 。

如果 $s_1[i] = s_2[i]$ ，则不需要交换，直接跳过即可。如果 $s_1[i] \neq s_2[i]$ ，则需要交换，我们统计 $s_1[i]$ 和 $s_2[i]$ 的组合情况，即 $s_1[i] = x$ 且 $s_2[i] = y$ 的情况，记为 $xy$ ，对于 $s_1[i] = y$ 且 $s_2[i] = x$ 的情况，记为 $yx$ 。

如果 $xy + yx$ 为奇数，则无法完成交换，返回 $-1$ 。如果 $xy + yx$ 为偶数，则需要交换的次数为 $\left \lfloor \frac{x}{2} \right \rfloor$ + $\left \lfloor \frac{y}{2} \right \rfloor$ + $xy \bmod{2}$ + $yx \bmod{2}$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $s_1$ 和 $s_2$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate an understanding of greedy algorithms and invariant validation.
question_mark
Look for an ability to handle edge cases like unequal counts of 'x' or 'y' in the two strings.
question_mark
Candidates who struggle with the swap count calculation or the impossibility check may need further guidance.

warning

常见陷阱

外企场景

error
Failing to check for the basic condition of equal 'x' and 'y' counts in both strings, which leads to unnecessary work or incorrect answers.
error
Overcomplicating the swap logic or not considering the invariant validation that matches mismatched pairs correctly.
error
Not properly handling edge cases where strings are already equal or impossible to solve.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Strings of larger lengths, requiring optimization of the greedy approach.
arrow_right_alt
Introducing characters beyond 'x' and 'y' and extending the logic to handle more characters.
arrow_right_alt
Modifying the problem to allow swapping within the same string.

help

常见问题

外企场景

继续练习

#1903 字符串中的最大奇数 #1927 求和游戏 #2038 如果相邻两个颜色均相同则删除当前颜色