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.
Example1
Input: s1 = "xx", s2 = "yy"
Output: 1
Explanation:
Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".
Example2
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.
Example3
Input: s1 = "xx", s2 = "xy"
Output: -1
Example4
Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
Output: 4
class Solution
{
public:
int minimumSwap(string s1, string s2)
{
int l = s1.length();
int count = 0;
// First check if its possible or not
int cnt_x = 0, cnt_y = 0;
for (int i = 0; i < l; i++)
{
if (s1[i] == 'x')
cnt_x++;
else
cnt_y++;
if (s2[i] == 'x')
cnt_x++;
else
cnt_y++;
}
if (cnt_x % 2 == 1)
return -1;
// Compare to strings and get rid of equal char
string _s1 = "",
_s2 = "";
for (int i = 0; i < l; i++)
{
if (s1[i] == s2[i])
{
continue;
}
else
{
_s1 += s1[i];
_s2 += s2[i];
}
}
// while (s1, s2's length > 0)
while (_s1.length() > 0)
{
// iteratively doing same logic
// logic -> take s1[0] and find nearest different char in s1 then we call it s1[n]
// swap (s1[n], s2[0]) then we can remove 2 char from both s1, s2
// renew s1, s2, and count += 1
int n = 0;
for (int i = 1; i < _s1.length(); i++)
{
if (_s1[0] == _s1[i])
{
n += i;
break;
}
}
swap(_s1[n], _s2[0]);
string t_s1 = "", t_s2 = "";
for (int i = 0; i < _s1.length(); i++)
{
if (_s1[i] == _s2[i])
{
continue;
}
else
{
t_s1 += _s1[i];
t_s2 += _s2[i];
}
}
_s1 = t_s1;
_s2 = t_s2;
count++;
}
return count;
}
};
At first, I tried to find out some rules of this problem...
I think it tooks maybe 5 to 10 mins? I found that the problem have same iterative logic in it.
First of all I can figured it out whether this those two strings can be solved or not.
Secondly I can do the logic.
The logic, at first, find out same chars in same index.
Then I remake two strings don't care about same elements so I got two new strings.
So, maybe there were new_s1 = "xy" new_s2 = "yx"
, from the point of view of new_s1 I just want to swap the nearest elements with the new_s2[0]
cause by doing this I can make two pares of chars in both strings!
It is finished.
I just need to iterate this logic if the new_s1
and new_s2
's lengths bigger than 0.