Given two binary strings A and B of length N, the task is to convert the string A to B by either flipping any character of A or swapping adjacent characters of A minimum number of times. If it is not possible to make both the strings equal, print -1.
Examples:
Input: A = “10010010”, B = “00001000”
Output: 3
Explanation:
Operation 1: Flipping A[0] modifies A to “00010010”.
Operation 2: Flipping A[6] modifies A to “00010000”.
Operation 3: Swapping A[3] and A[4] modifies A to “00001000”
Therefore, the total number of operations is 3.Input: A = “11”, B = “00”
Output: 3
Approach: The idea is to traverse the string A and try to make the same-indexed characters equal by first checking for the condition of swapping the adjacent characters. If the characters can not be made equal by this operation, then flip the character. Follow the steps below to solve the problem:
- Initialize a variable, say ans, to store the required result.
- Traverse the string A using a variable, say i, and perform the following operations:
- If A[i] is equal to B[i], then continue to the next iteration in the loop.
- Otherwise, if A[i] is equal to B[i + 1] and A[i + 1] is equal to B[i], then swap the characters and increment i and ans by 1.
- Otherwise, if A[i] is not equal to B[i], then flip the current bit and increment ans by 1.
- Print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum operations// required to convert string A to Bint minimumOperation(string a, string b){ // Store the size of the string int n = a.length(); int i = 0; // Store the required result int minoperation = 0; // Traverse the string, a while (i < n) { // If a[i] is equal to b[i] if (a[i] == b[i]) { i = i + 1; continue; } // Check if swapping adjacent // characters make the same-indexed // characters equal or not else if (a[i] == b[i + 1] && a[i + 1] == b[i] && i < n - 1) { minoperation++; i = i + 2; } // Otherwise, flip the current bit else if (a[i] != b[i]) { minoperation++; i = i + 1; } else { ++i; } } // Print the minimum number of operations cout << minoperation;}// Driver Codeint main(){ // Given Input string a = "10010010", b = "00001000"; // Function Call minimumOperation(a, b); return 0;} |
Java
// Java program for the above approachpublic class GFG{ // Function to find minimum operations// required to convert string A to Bstatic void minimumOperation(String a, String b){ // Store the size of the string int n = a.length(); int i = 0; // Store the required result int minoperation = 0; // Traverse the string, a while (i < n) { // If a[i] is equal to b[i] if (a.charAt(i) == b.charAt(i)) { i = i + 1; continue; } // Check if swapping adjacent // characters make the same-indexed // characters equal or not else if (a.charAt(i) == b.charAt(i + 1) && a.charAt(i + 1) == b.charAt(i) && i < n - 1) { minoperation++; i = i + 2; } // Otherwise, flip the current bit else if (a.charAt(i) != b.charAt(i)) { minoperation++; i = i + 1; } else { ++i; } } // Print the minimum number of operations System.out.println(minoperation);}// Driver Codepublic static void main(String []args){ // Given Input String a = "10010010", b = "00001000"; // Function Call minimumOperation(a, b);}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find minimum operations# required to convert A to Bdef minimumOperation(a, b): # Store the size of the string n = len(a) i = 0 # Store the required result minoperation = 0 # Traverse the string, a while (i < n): # If a[i] is equal to b[i] if (a[i] == b[i]): i = i + 1 continue # Check if swapping adjacent # characters make the same-indexed # characters equal or not elif (a[i] == b[i + 1] and a[i + 1] == b[i] and i < n - 1): minoperation += 1 i = i + 2 # Otherwise, flip the current bit elif (a[i] != b[i]): minoperation += 1 i = i + 1 else: i+=1 # Print the minimum number of operations print (minoperation)# Driver Codeif __name__ == '__main__': # Given Input a = "10010010" b = "00001000" # Function Call minimumOperation(a, b) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find minimum operations// required to convert string A to Bstatic void minimumOperation(string a, string b){ // Store the size of the string int n = a.Length; int i = 0; // Store the required result int minoperation = 0; // Traverse the string, a while (i < n) { // If a[i] is equal to b[i] if (a[i] == b[i]) { i = i + 1; continue; } // Check if swapping adjacent // characters make the same-indexed // characters equal or not else if (a[i] == b[i + 1] && a[i + 1] == b[i] && i < n - 1) { minoperation++; i = i + 2; } // Otherwise, flip the current bit else if (a[i] != b[i]) { minoperation++; i = i + 1; } else { ++i; } } // Print the minimum number of operations Console.WriteLine(minoperation);}// Driver Codepublic static void Main(){ // Given Input string a = "10010010", b = "00001000"; // Function Call minimumOperation(a, b);}}// This code is contributed by ankThon |
Javascript
<script>// Javascript program for the above approach// Function to find minimum operations// required to convert string A to Bfunction minimumOperation(a, b){ // Store the size of the string var n = a.length; var i = 0; // Store the required result var minoperation = 0; // Traverse the string, a while (i < n) { // If a[i] is equal to b[i] if (a[i] == b[i]) { i = i + 1; continue; } // Check if swapping adjacent // characters make the same-indexed // characters equal or not else if (a[i] == b[i + 1] && a[i + 1] == b[i] && i < n - 1) { minoperation++; i = i + 2; } // Otherwise, flip the current bit else if (a[i] != b[i]) { minoperation++; i = i + 1; } else { ++i; } } // Print the minimum number of operations document.write(minoperation);}// Driver Code // Given Input var a = "10010010", b = "00001000"; // Function Call minimumOperation(a, b); </script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
