You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].
Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.
Example 1:
Input: s1 = "xx", s2 = "yy" Output: 1 Explanation: Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".
Example 2:
Input: s1 = "xy", s2 = "yx" Output: 2 Explanation: Swap s1[0] and s2[0], s1 = "yy", s2 = "xx". Swap s1[0] and s2[1], s1 = "xy", s2 = "xy". Note that you cannot swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.
Example 3:
Input: s1 = "xx", s2 = "xy" Output: -1
Constraints:
1 <= s1.length, s2.length <= 1000s1.length == s2.lengths1, s2 only contain 'x' or 'y'.Problem Overview: You get two equal-length strings s1 and s2 containing only x and y. A swap exchanges characters between the two strings at different indices. The goal is to compute the minimum number of swaps needed to make the strings identical, or return -1 if it cannot be done.
Approach 1: Count Mismatches and Resolve by Swaps (Greedy) (Time: O(n), Space: O(1))
Scan both strings once and track mismatched pairs. Only two mismatch types matter: xy (where s1[i] = x and s2[i] = y) and yx. Two xy mismatches can be fixed with one swap, and the same applies to two yx mismatches. The tricky case occurs when one xy and one yx remain. Fixing that pair requires two swaps. The formula becomes swaps = xy/2 + yx/2 + 2*(xy%2). If the total mismatches xy + yx is odd, forming valid pairs is impossible, so return -1. This approach works because each swap resolves two symmetric mismatches. The algorithm only uses counters and a single pass over the strings. It relies on simple counting and greedy pairing, which fits well with problems involving greedy reasoning and string traversal.
Approach 2: Bit Manipulation and Lookup (Time: O(n), Space: O(1))
You can encode each mismatch pair as a small integer using bit operations. Map characters to bits (x = 0, y = 1) and combine the pair using (a << 1) | b. This produces four possible values representing xx, xy, yx, and yy. Only xy and yx contribute to the swap count, so maintain counters indexed by the encoded value. After processing the entire string, apply the same pairing logic used in the greedy approach: resolve pairs of identical mismatches first, then handle the leftover cross pair requiring two swaps. Bit encoding avoids string comparisons and can slightly simplify branching logic in tight loops. This technique is common when solving character-pair problems using math and bit tricks.
Recommended for interviews: The mismatch-count greedy solution is the one interviewers expect. It shows you recognize the structure of the problem and reduce it to counting two mismatch types. The bit-manipulation variant is a neat optimization, but the core insight remains the same: mismatches must be paired, and the final cross pair costs two swaps.
To solve this problem, we need to address mismatched positions in the strings s1 and s2. There are only two mismatched combinations to consider: 'x' in s1 with 'y' in s2 (noted as xy), and 'y' in s1 with 'x' in s2 (noted as yx). Our goal is to transform these mismatches into matches with the minimum number of swaps.
Each xy and yx mismatch can be resolved by one swap if there are an even number of them. If there is an odd number of both, we need an extra step to balance, totaling two more swaps. If they are unequal and one is odd while the other is even, it's impossible to make them the same.
The function counts the mismatches xy and yx. If their total is odd, it's impossible to balance, so return -1. Otherwise, resolve pairs of mismatches directly and handle one leftover mismatch with two swaps. The main function is a simple example to test the logic.
Time Complexity: O(n) where n is the length of s1 (and s2).
Space Complexity: O(1) since no extra space is used except for counters.
This approach employs bit manipulation techniques combined with a lookup strategy to optimize comparing positions and counting mismatches. However, given the content is exclusively 'x' and 'y', practical gains over simpler counting may not be significant. Still, this can offer a different conceptual perspective.
Bit manipulation would not provide significant improvement over counting mismatches for strings of modest length with binary data.
Time Complexity and Space Complexity would remain essentially O(n) and O(1) respectively due to nature of bit operations and fixed overhead.
According to the problem description, both strings s_1 and s_2 contain only the characters x and y, and they have the same length. Therefore, we can match the characters in s_1 and s_2 one by one, i.e., s_1[i] and s_2[i].
If s_1[i] = s_2[i], no swap is needed, and we can skip to the next character. If s_1[i] neq s_2[i], a swap is needed. We count the combinations of s_1[i] and s_2[i]: if s_1[i] = x and s_2[i] = y, we denote it as xy; if s_1[i] = y and s_2[i] = x, we denote it as yx.
If xy + yx is odd, it is impossible to complete the swaps, and we return -1. If xy + yx is even, the number of swaps needed is \left \lfloor \frac{xy}{2} \right \rfloor + \left \lfloor \frac{yx}{2} \right \rfloor + xy bmod{2} + yx bmod{2}.
The time complexity is O(n), where n is the length of the strings s_1 and s_2. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Count mismatches and resolve by swaps | Time Complexity: O(n) where n is the length of s1 (and s2). |
| Bit manipulation and lookup | Time Complexity and Space Complexity would remain essentially O(n) and O(1) respectively due to nature of bit operations and fixed overhead. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count mismatches and greedy pairing | O(n) | O(1) | Best general solution. Simple logic, minimal memory, ideal for interviews. |
| Bit manipulation with encoded pairs | O(n) | O(1) | Useful when implementing compact mismatch tracking or optimizing comparisons. |
Leetcode 1247: Minimum Swaps to Make Strings Equal • Algorithms Casts • 8,221 views views
Watch 9 more video solutions →Practice Minimum Swaps to Make Strings Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor