Skip to main content
Talentd

Minimum Swaps to Make Strings Equal - Solution & Explanation

MediumMathStringGreedy19 min readAsked at: Microsoft, Goldman Sachs, Google +1
Practice this problem

Problem Statement

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 <= 1000
  • s1.length == s2.length
  • s1, s2 only contain 'x' or 'y'.

Approach Overview

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.

Approach 1: Count mismatches and resolve by 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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Bit manipulation and lookup

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity and Space Complexity would remain essentially O(n) and O(1) respectively due to nature of bit operations and fixed overhead.

Try this approach in the editor →

Approach 3: Greedy

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).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Count mismatches and resolve by swaps

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.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Count mismatches and greedy pairingO(n)O(1)Best general solution. Simple logic, minimal memory, ideal for interviews.
Bit manipulation with encoded pairsO(n)O(1)Useful when implementing compact mismatch tracking or optimizing comparisons.

Video Solution

Leetcode 1247: Minimum Swaps to Make Strings Equal • Algorithms Casts • 8,235 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Swaps to Make Strings Equal easy or hard?
The problem is rated Medium because the implementation is simple but the insight about pairing mismatches is not immediately obvious. Once you recognize the xy and yx pattern, the greedy formula becomes straightforward.
Minimum Swaps to Make Strings Equal Python/Java solution
In Python or Java, iterate through both strings and count xy and yx mismatches. Compute swaps using xy/2 + yx/2 + 2*(xy%2), and return -1 if (xy + yx) is odd. The implementation is short and runs in O(n) time.
How to solve Minimum Swaps to Make Strings Equal in O(n)?
Iterate through both strings and count mismatches where s1[i] != s2[i]. Track how many are xy and how many are yx. Resolve pairs of the same type using one swap each, and if one xy and one yx remain, add two swaps. If the total number of mismatches is odd, return -1.
What is the best approach for Minimum Swaps to Make Strings Equal?
The best approach counts two mismatch types: xy and yx. Each pair of identical mismatches can be fixed with one swap, while one remaining xy and one yx require two swaps. The final formula is xy/2 + yx/2 + 2*(xy%2). This greedy counting method runs in O(n) time and O(1) space.
Is Minimum Swaps to Make Strings Equal asked at Google/Amazon/Meta?
String mismatch and greedy swap problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants test whether candidates can reduce character transformations to counting patterns and reasoning about minimal operations.
What data structure is used in Minimum Swaps to Make Strings Equal?
The problem does not require complex data structures. Most solutions use simple integer counters while scanning the strings. Some implementations encode character pairs using bit manipulation for faster lookup.
What is the time complexity of Minimum Swaps to Make Strings Equal?
The optimal solution runs in O(n) time because you scan both strings once to count mismatches. Only constant extra variables are used, so the space complexity is O(1).

Ready to solve this problem?

Practice Minimum Swaps to Make Strings Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Determine if Two Strings Are Close

Next

Make Number of Distinct Characters Equal