Greedy: Minimum swaps to make strings equal

Problem Statement:

You are given 2 strings, s1 and s2 of same size of letter x and y.

You need make both of the strings equal by swapping any two characters that below to different string.

Example:

Input: s1 = "xx" s2 ="yy"

Output: 1

Explanation: swap s1[0] and s2[1] to make the same string "yx"

Solution Explanation:

We will use greedy approach to solve the problem.

In this approach, if there is a mismatch then the only option is to swap.

So our result should return how many mismatch pairs are there and the minimum number of swaps required.

So there are 3 possibility:

If the sum of xy +yx is odd, then it is not possible to make the strings as equal, return -1.

if there are same mismatch, then it can be resolved with 1 swap

If there is one xy and one yx, then it needs 2 swaps.

So the final formula will be : xy/2 + yx/2 + (xy%2)*2

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(string s1, string s2) 
{
    int xy = 0;
    int yx = 0;
    int n = s1.size();

    for(int i=0;i<n;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/2 + yx/2 + (xy%2)*2;
}

int main()
{

    string s1 = "xx";
    string s2 = "yy";

    cout << solution(s1, s2) << '\n';

    return 0;
}

Output

1