# Minimum Swaps to Make Strings Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-swaps-to-make-strings-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-swaps-to-make-strings-equal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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'`.

# Approaches
## Brute-Force BFS
This approach models the problem as finding the shortest path in a state-space graph. Each state is a pair of strings `(s1, s2)`, and an edge represents a single swap operation. We use Breadth-First Search (BFS) to explore the states level by level, where each level corresponds to one additional swap. The first time we reach a state where `s1` equals `s2`, we have found the minimum number of swaps.
**Time:** Exponential, roughly O(N² * S), where S is the number of reachable states. The state space can be as large as 2^(2N), making this approach impractical. · **Space:** Exponential, O(S * N), where S is the number of reachable states. Storing the visited states and the queue requires an enormous amount of memory.
**Pros:** Conceptually simple as it's a direct application of BFS for shortest path problems.; Guaranteed to find the optimal solution if it could run to completion.
**Cons:** Extremely inefficient in both time and space.; Will cause a 'Time Limit Exceeded' error for all but the smallest inputs due to the massive state space.
### Explanation
The brute-force method involves exploring every possible sequence of swaps. We can think of this as a graph problem where nodes are pairs of strings `(s1, s2)` and edges are swaps. The goal is to find the shortest path from the initial state to any state `(s, s)`. BFS is a standard algorithm for finding the shortest path in an unweighted graph.

We start with the initial `(s1, s2)` in a queue. To avoid infinite loops and redundant computations, we use a `Set` to keep track of visited states. In each step, we dequeue a state, generate all possible next states by performing one valid swap (`s1[i]` with `s2[j]`), and enqueue any new, unvisited states. The number of swaps is tracked along with the states. The first time we find a state where the two strings are equal, we have our answer. However, the number of possible states and the number of potential swaps from each state (`N*N`) make this approach computationally infeasible for the given constraints.
### Algorithm
- Create a queue and add the initial state `(s1, s2, 0)` where 0 is the number of swaps.
- Create a set `visited` to store string pairs that have been processed.
- Add the initial pair `(s1, s2)` to `visited`.
- While the queue is not empty:
    - Dequeue the current state `(curr_s1, curr_s2, swaps)`.
    - If `curr_s1` equals `curr_s2`, return `swaps`.
    - For each possible index `i` from 0 to N-1:
        - For each possible index `j` from 0 to N-1:
            - Create new strings `new_s1` and `new_s2` by swapping `curr_s1[i]` and `curr_s2[j]`.
            - If the pair `(new_s1, new_s2)` is not in `visited`:
                - Add `(new_s1, new_s2)` to `visited`.
                - Enqueue `(new_s1, new_s2, swaps + 1)`.
- Return -1 if the queue empties.

## Greedy Approach with Mismatch Lists
A more targeted approach is to focus only on the positions where the strings differ. We can identify all such mismatches, categorize them into two types (`'x'-'y'` and `'y'-'x'`), and store their indices in lists. Then, we can greedily count the most efficient swaps (those that fix two mismatches at once). This avoids the massive state-space search of the brute-force method.
**Time:** O(N), where N is the length of the strings. We perform a single pass to populate the lists, followed by O(1) calculations. · **Space:** O(N), where N is the string length. In the worst case, all characters are mismatched, so the lists would store up to N indices.
**Pros:** Significantly more efficient than brute-force, with linear time complexity.; Correctly implements the core logic for solving the problem by focusing on mismatches.
**Cons:** Uses O(N) extra space to store the indices of mismatches, which is not strictly necessary.
### Explanation
This approach improves upon brute-force by using problem-specific insights. We only need to care about positions `i` where `s1[i] != s2[i]`.

1.  **Identify Mismatches**: We iterate through the strings once and create two lists of indices: one for `s1[i] = 'x', s2[i] = 'y'` mismatches (`xy_indices`) and one for `s1[i] = 'y', s2[i] = 'x'` mismatches (`yx_indices`).

2.  **Check Possibility**: A solution is possible only if the total count of 'x's and 'y's across both strings is even. This is equivalent to the total number of mismatches being even. So, if `xy_indices.size() + yx_indices.size()` is odd, we return -1.

3.  **Count Swaps**: 
    - Two 'xy' mismatches can be resolved with one swap. The number of such swaps is `xy_indices.size() / 2`.
    - Similarly, two 'yx' mismatches can be resolved with one swap, contributing `yx_indices.size() / 2` swaps.
    - If after pairing them up, we are left with one 'xy' mismatch and one 'yx' mismatch (i.e., `xy_indices.size()` is odd), it takes two additional swaps to resolve them.

The total minimum swaps is the sum of these counts.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int minimumSwap(String s1, String s2) {
        List<Integer> xy_indices = new ArrayList<>();
        List<Integer> yx_indices = new ArrayList<>();

        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == 'x' && s2.charAt(i) == 'y') {
                xy_indices.add(i);
            } else if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') {
                yx_indices.add(i);
            }
        }

        if ((xy_indices.size() + yx_indices.size()) % 2 != 0) {
            return -1;
        }

        int swaps = 0;
        swaps += xy_indices.size() / 2;
        swaps += yx_indices.size() / 2;

        if (xy_indices.size() % 2 == 1) {
            // One xy and one yx mismatch remain
            swaps += 2;
        }

        return swaps;
    }
}
```
### Algorithm
- Initialize two empty lists, `xy_indices` and `yx_indices`.
- Iterate through the strings from `i = 0` to `N-1`:
    - If `s1[i] == 'x'` and `s2[i] == 'y'`, add `i` to `xy_indices`.
    - If `s1[i] == 'y'` and `s2[i] == 'x'`, add `i` to `yx_indices`.
- Check for impossibility: If `(xy_indices.size() + yx_indices.size()) % 2 != 0`, return -1.
- Calculate swaps for pairs of same-type mismatches: `result = (xy_indices.size() / 2) + (yx_indices.size() / 2)`.
- If `xy_indices.size()` is odd, it means there's one 'xy' and one 'yx' mismatch remaining. Add 2 to the `result`.
- Return `result`.

## Optimal Single-Pass Counting Approach
This approach refines the greedy logic by realizing that we don't need to store the actual indices of the mismatches, only their counts. By performing a single pass through the strings, we can count the two types of mismatches and then use a mathematical formula to calculate the minimum swaps directly.
**Time:** O(N), for a single pass over the strings. · **Space:** O(1), as we only use a few integer variables to store the counts, regardless of the input size.
**Pros:** Optimal solution with O(N) time and O(1) space complexity.; Simple and elegant implementation once the logic is understood.
**Cons:** The mathematical formula might seem non-obvious without a careful analysis of the swap operations.
### Explanation
This is the most efficient solution. It's based on the same logic as the previous approach but optimizes space by avoiding the lists.

The core insights are:
- Any two mismatches of the same type (e.g., two `s1[i]='x', s2[i]='y'` pairs) can be resolved in one swap.
- Any two mismatches of different types (one `xy` and one `yx`) can be resolved in two swaps.

We iterate through the strings once, maintaining two counters: `xy_count` for `s1[i]='x', s2[i]='y'` mismatches, and `yx_count` for `s1[i]='y', s2[i]='x'` mismatches.

First, we check the impossibility condition: the total number of mismatches, `xy_count + yx_count`, must be even. If not, we return -1. An even total implies that `xy_count` and `yx_count` have the same parity (both even or both odd).

The total swaps can then be calculated:
- `xy_count / 2` swaps for the pairs of 'xy' mismatches.
- `yx_count / 2` swaps for the pairs of 'yx' mismatches.
- If `xy_count` is odd (meaning `yx_count` is also odd), we have one leftover 'xy' and one leftover 'yx' mismatch. These two require 2 swaps to resolve. This adds `(xy_count % 2) * 2` to the total.

A more concise mathematical formula that captures this logic is `(xy_count + 1) / 2 + (yx_count + 1) / 2`.

```java
class Solution {
    public int minimumSwap(String s1, String s2) {
        int xy_count = 0;
        int yx_count = 0;

        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            char c2 = s2.charAt(i);
            if (c1 == 'x' && c2 == 'y') {
                xy_count++;
            } else if (c1 == 'y' && c2 == 'x') {
                yx_count++;
            }
        }

        if ((xy_count + yx_count) % 2 != 0) {
            return -1;
        }

        int result = xy_count / 2;
        result += yx_count / 2;
        if (xy_count % 2 == 1) {
            // A remaining 'xy' and 'yx' mismatch requires 2 swaps.
            result += 2;
        }
        
        return result;
    }
}
```
### Algorithm
- Initialize `xy_count = 0` and `yx_count = 0`.
- Iterate through the strings from `i = 0` to `N-1`:
    - If `s1[i] == 'x'` and `s2[i] == 'y'`, increment `xy_count`.
    - If `s1[i] == 'y'` and `s2[i] == 'x'`, increment `yx_count`.
- If `(xy_count + yx_count) % 2 != 0`, return -1.
- Calculate and return the result using the formula: `(xy_count / 2) + (yx_count / 2) + (xy_count % 2) * 2`.

# Solutions
### Java

```java
class Solution { public int minimumSwap ( String s1 , String s2 ) { int xy = 0 , yx = 0 ; for ( int i = 0 ; i < s1 . length (); ++ i ) { char a = s1 . charAt ( i ), b = s2 . charAt ( i ); if ( a < b ) { ++ xy ; } if ( a > b ) { ++ yx ; } } if (( xy + yx ) % 2 == 1 ) { return - 1 ; } return xy / 2 + yx / 2 + xy % 2 + yx % 2 ; } }
```

### JavaScript

```javascript
var minimumSwap = function ( s1 , s2 ) { let xy = 0 , yx = 0 ; for ( let i = 0 ; i < s1 . length ; ++ i ) { const a = s1 [ i ], b = s2 [ i ]; if ( a < b ) { ++ xy ; } if ( a > b ) { ++ yx ; } } if (( xy + yx ) % 2 === 1 ) { return - 1 ; } return Math . floor ( xy / 2 ) + Math . floor ( yx / 2 ) + ( xy % 2 ) + ( yx % 2 ); };
```

### CPP

```cpp
class Solution { public: int minimumSwap ( string s1 , string s2 ) { int xy = 0 , yx = 0 ; for ( int i = 0 ; i < s1 . size (); ++ i ) { char a = s1 [ i ], b = s2 [ i ]; xy += a < b ; yx += a > b ; } if (( xy + yx ) % 2 ) { return - 1 ; } return xy / 2 + yx / 2 + xy % 2 + yx % 2 ; } };
```

### Python

```python
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
```