LeetCode 1247 - Minimum Swaps to Make Strings Equal

This problem asks us to determine the minimum number of swaps needed to make two strings, s1 and s2, equal. Both strings are of the same length and consist only of the characters "x" and "y".

leetcodemediummathstringgreedy

LeetCode Problem 1247

Difficulty: 🟡 Medium
Topics: Math, String, Greedy

Solution

Problem Understanding

This problem asks us to determine the minimum number of swaps needed to make two strings, s1 and s2, equal. Both strings are of the same length and consist only of the characters "x" and "y". The allowed swap operation is restricted: you may only swap characters between the two strings, not within the same string.

The input strings represent sequences of characters that may differ in certain positions. The output is a single integer representing the minimum number of swaps required to make the strings identical, or -1 if it is impossible to achieve equality.

Constraints tell us that the strings can have lengths up to 1000, so an O(n²) approach could be inefficient. Important edge cases include strings that are already equal (0 swaps required), strings that differ at an odd number of positions where matching is impossible, or strings that differ in only one position. The problem guarantees that both strings are non-empty and only contain "x" and "y".

Approaches

The brute-force approach would involve iterating through all possible swaps of characters between s1 and s2 until they match. For each mismatch, we would try all possible swaps, recursively or iteratively, to reach equality. While this approach is correct in principle, it is extremely inefficient due to the factorial number of possible swap sequences, leading to O(2^n) or worse time complexity.

The optimal solution relies on counting mismatched character pairs. There are two types of mismatches: xy (where s1 has x and s2 has y) and yx (where s1 has y and s2 has x). We can pair xy with xy or yx with yx to perform a single swap within the mismatched pairs. Any remaining mismatches after pairing must consist of exactly one xy and one yx, which can be resolved with two swaps. If the total number of mismatches is odd, it is impossible to equalize the strings, and we return -1.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Try all possible swaps between strings
Optimal O(n) O(1) Count xy and yx mismatches and calculate swaps

Algorithm Walkthrough

  1. Initialize two counters: xy and yx to zero. These will track the number of positions where s1[i] is x and s2[i] is y, and vice versa.
  2. Iterate through the strings using the same index i. For each position, check if s1[i] != s2[i].
  3. If there is a mismatch and s1[i] is x while s2[i] is y, increment the xy counter. If s1[i] is y while s2[i] is x, increment the yx counter.
  4. After iterating, check if (xy + yx) % 2 != 0. If the total number of mismatches is odd, return -1, since each swap resolves two mismatches.
  5. Calculate the minimum number of swaps. Each pair of xy mismatches can be resolved in one swap (xy // 2). Each pair of yx mismatches can be resolved similarly (yx // 2).
  6. If there is one remaining xy and one remaining yx, it will take two swaps to resolve them. This is equivalent to (xy % 2) * 2.
  7. Return the sum of these swaps as the minimum number of swaps required.

Why it works: Every swap resolves two mismatches optimally. Pairing mismatches reduces them efficiently, and the modulo check ensures impossibility is detected. This guarantees correctness without redundant operations.

Python Solution

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy = 0
        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
        
        swaps = (xy // 2) + (yx // 2) + (xy % 2) * 2
        return swaps

In this Python implementation, we first count mismatches as xy and yx. The modulo check ensures impossibility is caught early. The final swaps calculation handles both full pairs of mismatches and the case of one remaining unmatched pair, producing the minimum number of swaps.

Go Solution

func minimumSwap(s1 string, s2 string) int {
    xy, yx := 0, 0

    for i := 0; i < len(s1); 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
    }

    swaps := (xy / 2) + (yx / 2)
    if xy % 2 == 1 {
        swaps += 2
    }

    return swaps
}

In Go, the logic mirrors Python closely. We use integer division and modulo operators explicitly. Go does not require extra data structures since counters suffice, and strings are indexed directly.

Worked Examples

Example 1: s1 = "xx", s2 = "yy"

i s1[i] s2[i] xy yx
0 x y 1 0
1 x y 2 0

Swaps calculation: (2//2) + (0//2) + (2%2)*2 = 1 + 0 + 0 = 1. Output = 1.

Example 2: s1 = "xy", s2 = "yx"

i s1[i] s2[i] xy yx
0 x y 1 0
1 y x 1 1

Swaps calculation: (1//2) + (1//2) + (1%2)*2 = 0 + 0 + 2 = 2. Output = 2.

Example 3: s1 = "xx", s2 = "xy"

i s1[i] s2[i] xy yx
0 x x 0 0
1 x y 1 0

Total mismatches = 1, which is odd, so output = -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through both strings, n = length of strings
Space O(1) Only two counters are used, independent of input size

The linear time ensures that even the maximum constraint of 1000 characters is handled efficiently. Constant space makes this optimal in memory as well.

Test Cases

# Provided examples
assert Solution().minimumSwap("xx", "yy") == 1  # simple swap
assert Solution().minimumSwap("xy", "yx") == 2  # requires two swaps
assert Solution().minimumSwap("xx", "xy") == -1  # impossible

# Boundary values
assert Solution().minimumSwap("x", "x") == 0  # already equal
assert Solution().minimumSwap("y", "x") == -1  # impossible single char

# Larger inputs
assert Solution().minimumSwap("xy"*500, "yx"*500) == 1000  # alternating pattern
assert Solution().minimumSwap("xx"*500, "yy"*500) == 500  # large matching swaps
Test Why
"xx", "yy" Checks minimal swap calculation for simple two-character strings
"xy", "yx" Tests the two-swap scenario for alternating mismatches
"xx", "xy" Verifies detection of impossible swaps
"x", "x" Edge case of single character strings
"y", "x" Edge case with single mismatched character
Large inputs Stress test for performance and correctness

Edge Cases

  1. Already equal strings: For strings like "xx" and "xx", the algorithm correctly returns 0 because no mismatches exist and the swap logic naturally produces 0 swaps.
  2. Single mismatch impossible: For strings like "x" and "y", there is only one mismatch. Since swaps require two mismatched characters, the algorithm returns -1, correctly identifying impossibility.
  3. **Odd