Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1247.html
1247. Minimum Swaps to Make Strings Equal
Level
Medium
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 can’t 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
Example 4:
Input: s1 = “xxyyxyxyxx”, s2 = “xyyxyxxxyx”
Output: 4
Constraints:
1 <= s1.length, s2.length <= 1000
s1, s2
only contain'x'
or'y'
.
Solution
Loop over s1
and s2
and find the indices where the characters in s1
and s2
are different. Use two lists difX
and difY
to store the indices where the character in s1
is 'x'
and the character in s2
is 'y'
, and the indices where the character in s1
is 'y'
and the character in s2
is 'x'
, respectively.
Calculate sizeX = difX.size()
and sizeY = difY.size()
. If sizeX + sizeY
is odd, then it is impossible to swap the characters to make the two strings equal, so return -1. If sizeX + sizeY
is even, then sizeX
and sizeY
are both even or both odd. If both even, then return (sizeX + sizeY) / 2
. If both odd, then return (sizeX + sizeY) / 2 + 1
.
The explanation on the return value is as follows.
-
If
sizeX
andsizeY
are both even, then for thesizeX
indices where the character ins1
is'x'
and the character ins2
is'y'
, letindices1
andindices2
are two disjoint subsets ofdifX
such thatindices1
andindices2
have equal number of elements and the union ofindices1
andindices2
equalsdifX
. Replace each character ins1
at indices fromindices1
with each character ins2
at indices fromindices2
. Do the same for the othersizeY
indices as well. Thus the total number of swaps is(sizeX + sizeY) / 2
. -
If
sizeX
andsizeY
are both odd, then perform the steps above forsizeX - 1
indices fromdifX
andsizeY - 1
indices fromdifY
, and the total numbers of swaps is(sizeX + sizeY) / 2 - 1
so far. After that, there are two indices left, where the subsequences are"xy"
and"yx"
ins1
ands2
, respectively. To make the subsequences equal, two swaps are needed. Thus the total number of swaps is(sizeX + sizeY) / 2 + 1
.
-
class Solution { public int minimumSwap(String s1, String s2) { List<Integer> difX = new ArrayList<Integer>(); List<Integer> difY = new ArrayList<Integer>(); int length = s1.length(); for (int i = 0; i < length; i++) { char c1 = s1.charAt(i), c2 = s2.charAt(i); if (c1 != c2) { if (c1 == 'x') difX.add(i); else difY.add(i); } } int sizeX = difX.size(), sizeY = difY.size(); if ((sizeX + sizeY) % 2 != 0) return -1; else if (sizeX % 2 == 0) return (sizeX + sizeY) / 2; else return (sizeX + sizeY) / 2 + 1; } }
-
// OJ: https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/ // Time: O(N) // Space: O(1) class Solution { public: int minimumSwap(string a, string b) { int x = 0, y = 0, ans = 0; for (int i = 0; i < a.size(); ++i) { if (a[i] == b[i]) continue; if (a[i] == 'x') ++x; else ++y; if (x == 2) ++ans, x = 0; if (y == 2) ++ans, y = 0; } if (x != y) return -1; return x ? ans + 2 : ans; } };
-
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 ############ # 1247. Minimum Swaps to Make Strings Equal # https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/ class Solution: def minimumSwap(self, s1: str, s2: str) -> int: counter1, counter2 = Counter(s1), Counter(s2) if (counter1["x"] + counter2["x"]) % 2 and (counter1["y"] + counter2["y"]) % 2: return -1 mp1, mp2 = Counter(), Counter() res = 0 for c1,c2 in zip(s1,s2): if c1 != c2: if mp1[c1] > 0 and mp2[c2] > 0: mp1[c1] -= 1 mp2[c2] -= 1 else: mp1[c1] += 1 mp2[c2] += 1 res += 1 return res
-
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); };