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: Math
if s1[i] == s2[i] than no need to swap, so we can only look for
case1. s1[i] = x, s2[i] = y, xy
case2. s1[i] = y, s2[i] = x, yx
If case1 + case2 is odd, then there’s no solution.
Otherwise we can use one swap to fix two xys (or two yxs)
xx, yy => xy, yx
One special case is there an extra xy and and extra yx, which takes two swaps
xy, yx => yy, xx => xy, xy
Finally,
ans = (case1 + 1) / 2 + (case2 + 1) / 2
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int minimumSwap(string s1, string s2) { int xy = 0; int yx = 0; for (int i = 0; i < s1.length(); ++i) { if (s1[i] == 'x' && s2[i] == 'y') ++xy; if (s1[i] == 'y' && s2[i] == 'x') ++yx; } if ((xy + yx) % 2) return -1; return (xy + 1) / 2 + (yx + 1) / 2; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment