Minimum Swaps to Make Strings Equal

medium greedy math string

Problem

You are given two strings s1 and s2 of equal length consisting only of the letters 'x' and 'y'. In one operation you may swap any one character of s1 with any one character of s2. Return the minimum number of swaps required to make the two strings equal, or -1 if it is impossible.

Inputs1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"

Output4

Only mismatched positions matter. Count positions of type xy (s1='x', s2='y') and yx (s1='y', s2='x'). Each pair of same-type mismatches costs 1 swap; one leftover xy plus one leftover yx costs 2 swaps.

s1 (x / y characters)

s2 (x / y characters)

def minimum_swap(s1, s2):
    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 == 1:
        return -1
    return xy // 2 + yx // 2 + 2 * (xy % 2)

function minimumSwap(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 === 1) return -1;
  return Math.floor(xy / 2) + Math.floor(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++) {
            if (s1.charAt(i) == 'x' && s2.charAt(i) == 'y') xy++;
            else if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') yx++;
        }
        if ((xy + yx) % 2 == 1) return -1;
        return xy / 2 + yx / 2 + 2 * (xy % 2);
    }
}

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

Explanation

Only positions where the two strings differ matter. At every such position the pattern is either xy (s1 has 'x', s2 has 'y') or yx (s1 has 'y', s2 has 'x'). We just count how many of each, calling them xy and yx.

Here is the key insight: two mismatches of the same type can be fixed with a single swap. For example, two xy positions become aligned by swapping one character across, so every pair of same-type mismatches costs exactly 1 swap. That gives xy/2 + yx/2 swaps.

What about leftovers? If xy is odd, there is one stray xy left, and (because the total must be even) one stray yx as well. A stray xy plus a stray yx can be resolved, but it takes 2 swaps, not 1 — that's the 2 * (xy % 2) term.

If the total number of mismatches xy + yx is odd, they can never pair up, so the answer is -1.

Example: the given strings produce xy = 3 and yx = 3. Same-type pairs give 1 + 1 = 2 swaps, and the leftover odd xy/yx pair adds 2 more, for a total of 4.

Time: O(n) Space: O(1)