Problem of The Day: Minimum Swaps to Make Strings Equal

1 min read 361 words

Problem

LeetCode 1247

Given two equal-length strings s1, s2 of only 'x' and 'y', you can swap any char in s1 with any char in s2. Return the minimum swaps to make them equal, or -1 if impossible.

Key Idea

• Only mismatches matter:
  • xy: s1[i]='x', s2[i]='y'
  • yx: s1[i]='y', s2[i]='x'
• Pairing two same-type mismatches costs 1 swap.
• One leftover xy + one leftover yx costs 2 swaps.
• If total mismatches is odd → impossible.

Formula:

• swaps = xy//2 + yx//2 + 2*(xy%2)

Time O(n), Space O(1).

Code

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy_count = 0  # positions where s1 has 'x' and s2 has 'y'
        yx_count = 0  # positions where s1 has 'y' and s2 has 'x'

        for a, b in zip(s1, s2):
            if a != b:
                if a == 'x':
                    xy_count += 1
                else:
                    yx_count += 1

        # If total mismatches is odd, impossible to fix
        if (xy_count + yx_count) % 2 == 1:
            return -1

        # Each pair of same-type mismatches takes 1 swap
        # If there's one leftover of each type, they take 2 swaps
        return xy_count // 2 + yx_count // 2 + (xy_count % 2) * 2

Quick Checks

• “xx”, “yy” → xy=2 → swaps=1
• “xy”, “yx” → xy=1, yx=1 → swaps=2
• Odd mismatches → -1