Equalize strings

You are given two binary strings A and B and are required to make A equals to B. There are two types of operations:

  1. Swap any two adjacent bits or characters in the string A. The cost of this operation is 1 unit.
  2. Flip the bit or character of the string. The cost of this operation is 1 unit.

What is the minimum cost to make a string A equal to B?

Example:

Input: n = 4, source = "1101", target = "0011"
Output: 2

Approach

Java


public class EqualizeStrings {
    public static void main(String args[]) throws Exception {
        int n = 4;
        char[] source = "1101".toCharArray();
        char[] target = "0011".toCharArray();
        int operations = 0;
        int i = 0;
        while (i < n - 1) {
            if (source[i] == target[i]) {
                ++i;
                continue;
            }
            if ((source[i] == target[i + 1]) && (source[i + 1] == target[i])) {
                ++operations;
                source[i] = target[i + 1];
                source[i + 1] = target[i];
                i += 2;
                continue;
            }
            source[i] = target[i];
            ++operations;
            ++i;
        }
        if (i == (n - 1) && source[n - 1] != target[n - 1]) {
            ++operations;
        }
        System.out.println(operations);

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int equalizeString(int nstring sourcestring target)
{
    int operations = 0;
    int i = 0;
    while (i < n - 1)
    {
        //if character mathces then continue to
        //next position
        if (source[i] == target[i])
        {
            ++i;
            continue;
        }

        if ((source[i] == target[i + 1]) && (source[i + 1] == target[i]))
        {
            ++operations;
            source[i] = target[i + 1];
            source[i + 1] = target[i];
            i += 2;
            continue;
        }
        source[i] = target[i];
        ++operations;
        ++i;
    }
    if (i == (n - 1) && source[n - 1] != target[n - 1])
    {
        ++operations;
    }
    return operations;
}
int main()
{
    int n = 4;

    string source = "1101"target = "0011";

    cout << equalizeString(nsourcetarget<< "\n";

    return 0;
}


No comments:

Post a Comment