Minimum Swaps to Make Strings Equal

MEDIUM

Description

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

Checkout 3 different approaches to solve Minimum Swaps to Make Strings Equal. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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

Complexity Analysis

Time Complexity: O(N), for a single pass over the strings.Space Complexity: O(1), as we only use a few integer variables to store the counts, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Minimum Swaps to Make Strings Equal. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Minimum Swaps to Make Strings Equal

Patterns:

MathGreedy

Data Structures:

String

Companies:

J.P. Morgan |