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 <= 1000s1.length == s2.lengths1, s2only contain'x'or'y'.
Solutions
Solution 1: Greedy
According to the problem description, both strings s1 and s2 contain only the characters x and y, and they have the same length. Therefore, we can match the characters in s1 and s2 one by one, i.e., s1[i] and s2[i].
If s1[i] = s2[i], no swap is needed, and we can skip to the next character. If s1[i] ≠ s2[i], a swap is needed. We count the combinations of s1[i] and s2[i]: if s1[i] = x and s2[i] = y, we denote it as xy; if s1[i] = y and s2[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 xy⁄2 \right \rfloor + \left \lfloor yx⁄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: 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(code-box)
