Solution Explanation: Minimum Swaps to Make Strings Equal

This problem asks for the minimum number of swaps required to make two strings, s1 and s2, equal, where each string contains only 'x' and 'y' characters. We can only swap characters between the strings, not within a single string.

Approach:

The core idea is to analyze the differences between s1 and s2 efficiently. Instead of trying all possible swaps (which would be computationally expensive), we focus on pairs of characters that need swapping.

1. Counting Differences: Iterate through the strings simultaneously. If s1[i] != s2[i], we have a mismatch. We categorize these mismatches into two types:

   • xy: s1[i] is 'x' and s2[i] is 'y'.
   • yx: s1[i] is 'y' and s2[i] is 'x'. We count the number of xy and yx mismatches.

2. Checking Feasibility: If the total number of mismatches (xy + yx) is odd, it's impossible to make the strings equal. This is because we need an even number of swaps to change pairs of 'x' and 'y' in order to equalize the strings. In this case, return -1.

3. Calculating Minimum Swaps: If the total number of mismatches is even, we can calculate the minimum swaps needed:

   • xy // 2: Integer division of xy by 2. This represents the number of pairs of xy that can be swapped directly. Each pair requires one swap.
   • yx // 2: Same as above for yx mismatches.
   • xy % 2 + yx % 2: This accounts for any remaining xy or yx mismatches that are not part of a complete pair. Each of these requires one swap (and are paired with each other). This makes sure that the total mismatches are resolved, and as we know the total is even so we dont have a situation where we are stuck with one single mismatched character.

Time Complexity: O(n), where n is the length of the strings. We iterate through the strings once to count the mismatches.

Space Complexity: O(1). We only use a few constant extra variables to store the counts.

Code Examples in Multiple Languages:

The code implementation directly reflects the steps described above. Here's how it looks in several languages:

Python3:

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

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

C++:

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

Go:

func minimumSwap(s1 string, s2 string) int {
	xy, yx := 0, 0
	for i := range s1 {
		if s1[i] < s2[i] {
			xy++
		}
		if s1[i] > s2[i] {
			yx++
		}
	}
	if (xy+yx)%2 == 1 {
		return -1
	}
	return xy/2 + yx/2 + xy%2
}

JavaScript:

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

These code snippets all follow the same algorithmic strategy, making them concise and efficient. The slight variations are due to the syntactic differences between the programming languages.