Problem Description

You are given two strings s1 and s2 of equal length, containing only the characters 'x' and 'y'. You can swap any character from s1 with any character from s2 at the same index (i.e., swap s1[i] with s2[i] for any i). The goal is to make both strings equal using the minimum number of swaps.

Return the minimum number of swaps required to make s1 and s2 equal. If it is impossible, return -1.

• Both s1 and s2 have the same length, between 1 and 1000.
• Only the characters 'x' and 'y' are present in the strings.
• Each swap can only be performed between characters at the same index in s1 and s2.

Thought Process

The naive approach would be to try all possible swaps, but this quickly becomes infeasible as the string length increases. Instead, let's focus on the mismatches between the strings. At every position i, if s1[i] != s2[i], a swap is needed at some point to resolve the difference.

There are two types of mismatches:

• 'x' in s1 and 'y' in s2 (let's call this an xy mismatch)
• 'y' in s1 and 'x' in s2 (let's call this a yx mismatch)

Solution Approach

• Step 1: Count mismatches.
  • Iterate through the strings and count how many xy and yx mismatches there are.
• Step 2: Check for possibility.
  • If the total number of mismatches is odd (i.e., (xy + yx) is odd), it's impossible to make the strings equal, because each swap can only fix two mismatches at a time.
• Step 3: Calculate minimum swaps.
  • Every pair of xy mismatches can be fixed with one swap.
  • Every pair of yx mismatches can be fixed with one swap.
  • If there's one xy and one yx left (i.e., both counts are odd), it takes two swaps to fix both.
  • So, the formula is: (xy // 2) + (yx // 2) + 2 * (xy % 2)

This approach is efficient because it only requires a single pass to count mismatches and a simple calculation to get the answer.

Example Walkthrough

Let's consider s1 = "xxyyxyxyxx" and s2 = "xyyxyxxxyx".

• Compare each character at the same index:
• At positions where s1[i] != s2[i], count the type of mismatch:
• Suppose there are 4 xy mismatches and 3 yx mismatches.
• Since xy + yx = 7 (odd), it is impossible to make the strings equal, so return -1.
• If instead, there were 4 xy and 4 yx mismatches, then:
  • Each pair of xy (2 pairs) takes 2 swaps.
  • Each pair of yx (2 pairs) takes 2 swaps.
  • No mismatches left, so total swaps = 2 + 2 = 4.
• If there were 3 xy and 3 yx mismatches:
  • One pair of each (1 swap each), and the remaining one xy and one yx take 2 swaps.
  • Total swaps = 1 + 1 + 2 = 4.

Time and Space Complexity

• Brute-force approach:
  • Would involve trying all possible swap combinations, leading to exponential time complexity (O(2^n)), which is not feasible.
• Optimized approach (current solution):
  • Time Complexity: O(n) — We only need one pass through the strings to count mismatches.
  • Space Complexity: O(1) — Only two integer counters are used, regardless of input size.

Summary

By focusing on the types of mismatches between s1 and s2, we avoid brute-force approaches and achieve an efficient linear-time solution. The key insight is that swaps resolve mismatches in pairs, and an odd total means it's impossible. This approach is both simple and powerful, illustrating how recognizing problem structure can lead to elegant solutions.

Code Implementation

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy = yx = 0
        for a, b in zip(s1, s2):
            if a == 'x' and b == 'y':
                xy += 1
            elif a == 'y' and b == 'x':
                yx += 1
        if (xy + yx) % 2 != 0:
            return -1
        return (xy // 2) + (yx // 2) + 2 * (xy % 2)
      

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.size(); ++i) {
            if (s1[i] == 'x' && s2[i] == 'y') xy++;
            else if (s1[i] == 'y' && s2[i] == 'x') yx++;
        }
        if ((xy + yx) % 2 != 0) return -1;
        return (xy / 2) + (yx / 2) + 2 * (xy % 2);
    }
};
      

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 == 'x' && b == 'y') xy++;
            else if (a == 'y' && b == 'x') yx++;
        }
        if ((xy + yx) % 2 != 0) return -1;
        return (xy / 2) + (yx / 2) + 2 * (xy % 2);
    }
}
      

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