You are given two binary strings and and are required to make equals to . There are two types of operations:
- Swap any two adjacent bits or characters in the string . The cost of this operation is 1 unit.
- 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 n, string source, string target){int operations = 0;int i = 0;while (i < n - 1){//if character mathces then continue to//next positionif (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(n, source, target) << "\n";return 0;}
No comments:
Post a Comment