Problem

You are given two strings s1 and s2 of equal length consisting of letters "x" and "y" only. Your task is to make these two strings equal to each other. You can swap any two characters that belong to different strings, which means: swap s1[i] and s2[j].

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

Examples

Example 1

1
2
3

Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation: Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".

Example 2

1
2
3
4
5

Input: s1 = "xy", s2 = "yx"
Output: 2
Explanation: Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
Note that you cannot swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.

Example 3

1
2

Input: s1 = "xx", s2 = "xy"
Output: -1

Constraints

  • 1 <= s1.length, s2.length <= 1000
  • s1.length == s2.length
  • s1, s2 only contain 'x' or 'y'.

Solution

Method 1 – Greedy Counting

Intuition

Count mismatches: positions where s1[i] != s2[i]. There are two types: ‘xy’ and ‘yx’. Each pair of ‘xy’ and ‘yx’ can be fixed with one swap, and two of the same type need two swaps. If the total number of mismatches is odd, it’s impossible.

Approach

  1. Iterate through both strings, count ‘xy’ and ‘yx’ mismatches.
  2. If (xy + yx) is odd, return -1.
  3. The answer is (xy // 2) + (yx // 2) + 2 * (xy % 2).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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++;
            if (s1[i] == 'y' && s2[i] == 'x') yx++;
        }
        if ((xy + yx) % 2) return -1;
        return xy/2 + yx/2 + 2*(xy%2);
    }
};
1
2
3
4
5
6
7
8
9

func minimumSwap(s1, s2 string) int {
    xy, yx := 0, 0
    for i := range s1 {
        if s1[i] == 'x' && s2[i] == 'y' { xy++ }
        if s1[i] == 'y' && s2[i] == 'x' { yx++ }
    }
    if (xy+yx)%2 != 0 { return -1 }
    return xy/2 + yx/2 + 2*(xy%2)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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++;
            if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') yx++;
        }
        if ((xy + yx) % 2 != 0) return -1;
        return xy/2 + yx/2 + 2*(xy%2);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minimumSwap(s1: String, s2: String): Int {
        var xy = 0; var yx = 0
        for (i in s1.indices) {
            if (s1[i]=='x' && s2[i]=='y') xy++
            if (s1[i]=='y' && s2[i]=='x') yx++
        }
        if ((xy+yx)%2 != 0) return -1
        return xy/2 + yx/2 + 2*(xy%2)
    }
}
1
2
3
4
5
6
7
8

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
            if a == 'y' and b == 'x': yx += 1
        if (xy + yx) % 2: return -1
        return xy//2 + yx//2 + 2*(xy%2)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn minimum_swap(s1: String, s2: String) -> i32 {
        let (mut xy, mut yx) = (0, 0);
        for (a, b) in s1.chars().zip(s2.chars()) {
            if a == 'x' && b == 'y' { xy += 1; }
            if a == 'y' && b == 'x' { yx += 1; }
        }
        if (xy + yx) % 2 != 0 { return -1; }
        xy/2 + yx/2 + 2*(xy%2)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    minimumSwap(s1: string, s2: string): number {
        let xy = 0, yx = 0;
        for (let i = 0; i < s1.length; i++) {
            if (s1[i] === 'x' && s2[i] === 'y') xy++;
            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);
    }
}

Complexity

  • ⏰ Time complexity: O(n) — One pass through both strings.
  • 🧺 Space complexity: O(1) — Only counters used.