Minimum Swaps to Make Strings Equal

Med

#1164Time: 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.1 company

Patterns

Math Greedy

Data structures

String

Companies

J.P. Morgan

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int minimumSwap(String s1, String s2) {3        int xy_count = 0;4        int yx_count = 0;5 6        for (int i = 0; i < s1.length(); i++) {7            char c1 = s1.charAt(i);8            char c2 = s2.charAt(i);9            if (c1 == 'x' && c2 == 'y') {10                xy_count++;11            } else if (c1 == 'y' && c2 == 'x') {12                yx_count++;13            }14        }15 16        if ((xy_count + yx_count) % 2 != 0) {17            return -1;18        }19 20        int result = xy_count / 2;21        result += yx_count / 2;22        if (xy_count % 2 == 1) {23            // A remaining 'xy' and 'yx' mismatch requires 2 swaps.24            result += 2;25        }26        27        return result;28    }29}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

This approach improves upon brute-force by using problem-specific insights. We only need to care about positions i where s1[i] != s2[i].

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

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int minimumSwap(String s1, String s2) {6        List<Integer> xy_indices = new ArrayList<>();7        List<Integer> yx_indices = new ArrayList<>();8 9        for (int i = 0; i < s1.length(); i++) {10            if (s1.charAt(i) == 'x' && s2.charAt(i) == 'y') {11                xy_indices.add(i);12            } else if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') {13                yx_indices.add(i);14            }15        }16 17        if ((xy_indices.size() + yx_indices.size()) % 2 != 0) {18            return -1;19        }20 21        int swaps = 0;22        swaps += xy_indices.size() / 2;23        swaps += yx_indices.size() / 2;24 25        if (xy_indices.size() % 2 == 1) {26            // One xy and one yx mismatch remain27            swaps += 2;28        }29 30        return swaps;31    }32}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1var 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 ); };

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ; } }

1var 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 ); };

1class 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 ; } };

1class 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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.