Minimum Swaps to Make Strings Equal Leetcode Solution

Problem Statement

You are given two strings s1 and s2 of equal length consisting of letters “x” and “y” only. you can swap any two characters belong to different strings,
your task is to make both the string equal. return minimum number of swaps required to make both strings equal or -1 if it is impossible to make both strings equal.

Example

#1

s1 = "xx", s2 = "yy"

1

#2

s1 = "xy", s2 = "yx"

2

Approach (Greedy)

If we look at the characters in both the strings at some ith Index, we will find that there are only 4 possible pairs {s1[i],s2[i]}: {“x”,”x”},{“y,”y”},{“x”,”y”},{“y”,”x”}.
for the first two types of pairs s1[i] is equal to s2[i] (this is what we want), the number of swaps required will be zero for such cases.

for rest of the pairs we have s1[i] is not equal to s2[i], so we need to use swap operations.

we can use this in two ways :

(i) if we have 3rd (or 4th) type pair at both indexes i and j (i is not equal to j), if we swap s1[i] with s2[j] then s1[i] will become equal to s2[i](i.e. s[i]=s2[i])
and s1[j] will become equal to s2[j](i.e. s1[j]=s2[j]), it means in one move can make s1[i]=s2[i] and s1[j]=s2[j].

(ii) if we have 3rd type of pair at index i and 4th type of pair at some index j (or vice versa) : {“x”,”y”},{“y”,”x”}. so, to make s1[i]=s2[i] and
s1[j]=s2[j] we need to swap twice, first we need to swap s1[i] with s2[i], now pairs will look like : {“y”,”x”}, {“y,”x”}. now we need to swap s1[i] with s2[j] and we will get
s1[i]=s2[i] and s1[j]=s2[j].

as we can see the (i) type operation takes just 1 move to settle two indexes, so we will try to make (i) type operations as much as we can. we can easily get count of all
types of pairs. Let’s say we get count of {“x”,”y”} pairs =n1, count of {“y”,”x”} pairs =n2.
we can settle 2 pairs of type 3 in one swap. so the total swap we need to settle n1 pairs will be n1/2, if n1 is odd one pair will remain unsettled.

Similarly for n2 . if n1 and n2 both are odd we will get one pair of each unsettled so we can use (ii) type operation that requires 2 swaps to settle them.
otherwise, if the parity of n1 and n2 is not the same(i.e. n1 is odd and n2 is even) then we will get one pair that is not settled,
in that case, it will be impossible to make the strings equal.

Implementation

C++ Program for Minimum Swaps to Make Strings Equal Leetcode Solution

#include<bits/stdc++.h>
using namespace std;
int minimumSwap(string s1, string s2) 
{
    int xy_count=0,//count of {x,y} pairs
    yx_count=0,//count of {y,x} pairs
    n=s1.length();
    for(int i=0;i<n;i++)
    {
        if(s1[i]!=s2[i])
        {
            if(s1[i]=='x') xy_count++;
            else yx_count++;
        }
    }
    if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+(xy_count%2==1);//if parity of count of xy pair and yx pair is same 
    else return -1;
}

int main()
{
    string s1="xxxyy",s2="yyxxx";
    cout<<minimumSwap(s1,s2);
    return 0;
}

2

Java Program for Minimum Swaps to Make Strings Equal Leetcode Solution

class Rextester{
    
      public static int minimumSwap(String s1, String s2) 
      {
         
        int xy_count=0,//count of {x,y} pairs
        yx_count=0,//count of {y,x} pairs
        n=s1.length();
        for(int i=0;i<n;i++)
        {
            if(s1.charAt(i)!=s2.charAt(i))
            {
                if(s1.charAt(i)=='x') xy_count++;
                else yx_count++;
            }
        }

        //if parity of count of xy pair and yx pair is same 
        if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+((xy_count%2==1)?1:0);
        else return -1;
    }
    
    public static void main(String args[])
    {
       	String s1="xxxyy",s2="yyxxx";
        System.out.println(minimumSwap(s1,s2) );
    }
}

2

Complexity Analysis for Minimum Swaps to Make Strings Equal Leetcode Solution

Time Complexity

O(n) : Where n is the length of the string. As we are iterating both the string only once, hence time complexity will be O(n).

Space Complexity

O(1) : We are not using any extra space.