Welcome to Subscribe On Youtube
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
According to the problem description, both strings $s1$ and $s2$ only contain characters $x$ and $y$, and have the same length. Therefore, we can pair the characters in $s1$ and $s2$, i.e., $s1[i]$ and $s2[i]$.
If $s1[i] = s2[i]$, no swap is needed, and we can skip it. If $s1[i] \neq s2[i]$, a swap is needed. We count the combination of $s1[i]$ and $s2[i]$, i.e., the situation where $s1[i] = x$ and $s2[i] = y$, denoted as $xy$, and the situation where $s1[i] = y$ and $s2[i] = x$, denoted as $yx$.
If $xy + yx$ is odd, the swap cannot be completed, and we return $1$. If $xy + yx$ is even, the number of swaps needed is $\left \lfloor \frac{x}{2} \right \rfloor$ + $\left \lfloor \frac{y}{2} \right \rfloor$ + $xy \bmod{2}$ + $yx \bmod{2}$.
The time complexity is $O(n)$, where $n$ is the length of the strings $s1$ and $s2$. The space complexity is $O(1)$.

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; } }

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; } };

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

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 }

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); };