Minimum Swaps To Make Strings Equal - Leetcode Solution

Problem:

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 do this by swapping any two characters from both strings. You are allowed to make zero or more swaps. Return the minimum number of swaps needed to make the strings s1 and s2 equal. If it is impossible to make the strings equal, return -1.

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 characters from different strings.

Approach:

There are some cases to check to get a solution to this problem:

Case 1: check if both the strings have the same count of x and y character, if not return -1.

Case 2: If both strings have different x and y characters at the same index we need to swap these characters within those strings. In this case, we need to increment the swap count by 1. If the number of swaps counted is odd that indicates that the swapping is not possible.

Case 3: when the x and y position is different in both strings then we need to swap them in one string only and swap these characters in the second string at the same time. This will increment count by 1.

We will follow the approach mentioned above for the solution.

Algorithm:

If both strings have different numbers of "x" or "y" characters then it is not possible to make them equal, so return -1.

Initialize a variable cnt=0 which counts the number of swaps required to make the strings equal.

Loop through the length of the string s1.

Check if s1[i] != s2[i]. If true then we will follow case 2 or case 3 from approach mentioned above.

If none of the conditions is met then return cnt.

Solution:

Here is the python code for the above approach.

def minSwaps(s1: str, s2: str) -> int: x1, y1, x2, y2, n = 0, 0, 0, 0, len(s1)

for i in range(n):
    if s1[i] == 'x' and s2[i] == 'y':
        x1 += 1
    elif s1[i] == 'y' and s2[i] == 'x':
        y1 += 1
    elif s1[i] == 'y' and s2[i] == 'y':
        y2 += 1
    elif s1[i] == 'x' and s2[i] == 'x':
        x2 += 1

if (x1 + y1) % 2 != 0 or (x2 + y2) % 2 != 0 or x1 > y2 or y1 > x2:
    return -1

cnt = 0
cnt += x1//2 + y1//2 + (x1%2) * 2

return cnt 

Let's look at the time and space complexity of the solution.

Time Complexity:

The time complexity of the above solution is O(n) where n is the length of the strings s1 and s2. We are traversing through the length of these strings once.

Space Complexity:

The space complexity of the above solution is O(1).

Hence, we have solved the Minimum Swaps To Make Strings Equal problem with O(n) time complexity and O(1) space complexity using the above approach.

1