Algorithm
Problem Name: 1247. Minimum Swaps to Make Strings Equal
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 <= 1000s1, s2only contain'x'or'y'.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const minimumSwap = function (s1, s2) {
let x1 = 0 // number of 'x' in s1 (skip equal chars at same index)
let y1 = 0 // number of 'y' in s1 (skip equal chars at same index)
let x2 = 0 // number of 'x' in s2 (skip equal chars at same index)
let y2 = 0 // number of 'y' in s2 (skip equal chars at same index)
for (let i = 0; i < s1.length; i++) {
let c1 = s1.charAt(i)
let c2 = s2.charAt(i)
if (c1 == c2) {
// skip chars that are equal at the same index in s1 and s2
continue
}
if (c1 == 'x') {
x1++
} else {
y1++
}
if (c2 == 'x') {
x2++
} else {
y2++
}
} // end for
// After skip "c1 == c2", check the number of 'x' and 'y' left in s1 and s2.
if ((x1 + x2) % 2 != 0 || (y1 + y2) % 2 != 0) {
return -1 // if number of 'x' or 'y' is odd, we can not make s1 equals to s2
}
let swaps = Math.floor(x1 / 2) + Math.floor(y1 / 2) + (x1 % 2) * 2
// Cases to do 1 swap:
// "xx" => x1 / 2 => how many pairs of 'x' we have ?
// "yy" => y1 / 2 => how many pairs of 'y' we have ?
//
// Cases to do 2 swaps:
// "xy" or "yx" => x1 % 2
return swaps
}
Input
s1 = "xx", s2 = "yy"
Output
1
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minimumSwap(self, s1: str, s2: str, xy: int = 0, yx: int = 0) -> int:
for a, b in zip(s1, s2):
xy += a == "x" and b == "y"
yx += a == "y" and b == "x"
return (xy + yx) // 2 + (xy % 2) * 2 if xy % 2 == yx % 2 else -1
Input
s1 = "xx", s2 = "yy"
Output
1
#3 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _1247_MinimumSwapsToMakeStringsEqual
{
public int MinimumSwap(string s1, string s2)
{
if (s1.Length != s2.Length) return -1;
int xy = 0;
int yx = 0;
for (int 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 xy / 2 + yx / 2 + xy % 2 + yx % 2;
}
}
}
Input
s1 = "xy", s2 = "yx"
Output
2