Skip to content

1247. Minimum Swaps to Make Strings Equal

Description

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.

 

Example 1:

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

Example 2:

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:

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'.

Solutions

Solution 1: Greedy

Thinking

Matching positions need no swap. Mismatches are only \(xy\) and \(yx\). Two mismatches of the same kind swap in one move; one of each kind needs two; an odd total is impossible.

We count both kinds, reject an odd sum, and otherwise take each count halved plus at most one cross-type pair. The pairing does not depend on positions.

According to the problem description, both strings \(s_1\) and \(s_2\) contain only the characters \(x\) and \(y\), and they have the same length. Therefore, we can match the characters in \(s_1\) and \(s_2\) one by one, i.e., \(s_1[i]\) and \(s_2[i]\).

If \(s_1[i] = s_2[i]\), no swap is needed, and we can skip to the next character. If \(s_1[i] \neq s_2[i]\), a swap is needed. We count the combinations of \(s_1[i]\) and \(s_2[i]\): if \(s_1[i] = x\) and \(s_2[i] = y\), we denote it as \(xy\); if \(s_1[i] = y\) and \(s_2[i] = x\), we denote it as \(yx\).

If \(xy + yx\) is odd, it is impossible to complete the swaps, and we return \(-1\). If \(xy + yx\) is even, the number of swaps needed is \(\left \lfloor \frac{xy}{2} \right \rfloor + \left \lfloor \frac{yx}{2} \right \rfloor + xy \bmod{2} + yx \bmod{2}\).

The time complexity is \(O(n)\), where \(n\) is the length of the strings \(s_1\) and \(s_2\). The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xy = yx = 0
        for a, b in zip(s1, s2):
            xy += a < b
            yx += a > b
        if (xy + yx) % 2:
            return -1
        return xy // 2 + yx // 2 + xy % 2 + yx % 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 < b) {
                ++xy;
            }
            if (a > b) {
                ++yx;
            }
        }
        if ((xy + yx) % 2 == 1) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.size(); ++i) {
            char a = s1[i], b = s2[i];
            xy += a < b;
            yx += a > b;
        }
        if ((xy + yx) % 2) {
            return -1;
        }
        return xy / 2 + yx / 2 + xy % 2 + yx % 2;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func minimumSwap(s1 string, s2 string) int {
    xy, yx := 0, 0
    for i := range s1 {
        if s1[i] < s2[i] {
            xy++
        }
        if s1[i] > s2[i] {
            yx++
        }
    }
    if (xy+yx)%2 == 1 {
        return -1
    }
    return xy/2 + yx/2 + xy%2 + yx%2
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function minimumSwap(s1: string, s2: string): number {
    let xy = 0,
        yx = 0;

    for (let i = 0; i < s1.length; ++i) {
        const a = s1[i],
            b = s2[i];
        xy += a < b ? 1 : 0;
        yx += a > b ? 1 : 0;
    }

    if ((xy + yx) % 2 !== 0) {
        return -1;
    }

    return Math.floor(xy / 2) + Math.floor(yx / 2) + (xy % 2) + (yx % 2);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
var minimumSwap = function (s1, s2) {
    let xy = 0,
        yx = 0;
    for (let i = 0; i < s1.length; ++i) {
        const a = s1[i],
            b = s2[i];
        if (a < b) {
            ++xy;
        }
        if (a > b) {
            ++yx;
        }
    }
    if ((xy + yx) % 2 === 1) {
        return -1;
    }
    return Math.floor(xy / 2) + Math.floor(yx / 2) + (xy % 2) + (yx % 2);
};

Comments