Minimum substring flips required to convert given binary string to another
Given two binary strings A and B, the task is to find the minimum number of times a substring starting from the first character of A needs to be flipped, i.e. convert 1s to 0s and 0s to 1s, to convert A to B.
Examples:
Input: A = β0010β, B = β1011β
Output; 3
Explanation:
Step 1: Flip the entire string A. Therefore, A becomes β1101β .
Step 2: Flip the substring {A[0], A[2]}. Therefore, A becomes β0011β .
Step 3: Flip A[0]. Therefore, A becomes β1011β which is equal to B.
Therefore, the minimum number of operations required is 3.Input: A = β1010101β, B = β0011100β
Output: 5
Explanation:
Step 1: Flip the entiThehrefore, A becomes β0101010β³
Step 2: Flip substring {A[0], A[5]}. Therefore, A becomes β1010100β³
Step 3: Flip the substring {A[0], A[3]}. Therefore, A becomes β0101100β³
Step 4: Flip the substring {A[0], A[2]}. Therefore, A becomes β1011100β³
Step 5: Flip A[0]. Therefore, A becomes β0011100β which is equal to B.
Therefore, the minimum number of operations required is 5.
Approach: The idea is to initialize a variable that holds the last index at which character at A is different from the character at B. Then negate A from the 1st index to the last index. Repeat until both strings become equal. Follow the steps below to solve the problem:
- Initialize a variable last_index that holds the last index at which characters are different in A and B.
- Negate string A from the 1st index to last_index and increment the count of steps.
- Repeat the above steps until string A becomes equal to string B.
- Print the count of steps after both the strings are the same after performing the operations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that finds the minimum // number of operations required such // that string A and B are the same void findMinimumOperations(string a, string b) { // Stores the count of steps int step = 0; // Stores the last index whose // bits are not same int last_index; // Iterate until both string // are unequal while (a != b) { // Check till end of string to // find rightmost unequals bit for ( int i = 0; i < a.length(); i++) { // Update the last index if (a[i] != b[i]) { last_index = i; } } // Flipping characters up // to the last index for ( int i = 0; i <= last_index; i++) { // Flip the bit a[i] = (a[i] == '0' ) ? '1' : '0' ; } // Increasing steps by one step++; } // Print the count of steps cout << step; } // Driver Code int main() { // Given strings A and B string A = "101010" , B = "110011" ; // Function Call findMinimumOperations(A, B); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ // Function that finds the minimum // number of operations required such // that String A and B are the same static void findMinimumOperations( char [] a, char [] b) { // Stores the count of steps int step = 0 ; // Stores the last index whose // bits are not same int last_index = 0 ; // Iterate until both String // are unequal while (!Arrays.equals(a, b)) { // Check till end of String to // find rightmost unequals bit for ( int i = 0 ; i < a.length; i++) { // Update the last index if (a[i] != b[i]) { last_index = i; } } // Flipping characters up // to the last index for ( int i = 0 ; i <= last_index; i++) { // Flip the bit a[i] = (a[i] == '0' ) ? '1' : '0' ; } // Increasing steps by one step++; } // Print the count of steps System.out.print(step); } // Driver Code public static void main(String[] args) { // Given Strings A and B String A = "101010" , B = "110011" ; // Function Call findMinimumOperations(A.toCharArray(), B.toCharArray()); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach # Function that finds the minimum # number of operations required such # that string A and B are the same def findMinimumOperations(a, b): # Stores the count of steps step = 0 # Stores the last index whose # bits are not same last_index = 0 # Iterate until both string # are unequal while (a ! = b): a = [i for i in a] # Check till end of string to # find rightmost unequals bit for i in range ( len (a)): # Update the last index if (a[i] ! = b[i]): last_index = i # Flipping characters up # to the last index for i in range (last_index + 1 ): # Flip the bit if (a[i] = = '0' ): a[i] = '1' else : a[i] = '0' a = "".join(a) # Increasing steps by one step + = 1 # Print the count of steps print (step) # Driver Code if __name__ = = '__main__' : # Given strings A and B A = "101010" B = "110011" # Function Call findMinimumOperations(A, B) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; class GFG{ // Function that finds the minimum // number of operations required such // that string A and B are the same static void findMinimumOperations( string a, string b) { // Stores the count of steps int step = 0; // Stores the last index whose // bits are not same int last_index = 0; // Iterate until both string // are unequal while (a.Equals(b) == false ) { // Check till end of string to // find rightmost unequals bit for ( int i = 0; i < a.Length; i++) { // Update the last index if (a[i] != b[i]) { last_index = i; } } // Flipping characters up // to the last index char [] ch = a.ToCharArray(); for ( int i = 0; i <= last_index; i++) { // Flip the bit if (ch[i] == '0' ) { ch[i] = '1' ; } else { ch[i] = '0' ; } } a = new string (ch); // Increasing steps by one step++; } // Print the count of steps Console.WriteLine(step); } // Driver Code public static void Main() { // Given strings A and B string A = "101010" ; string B = "110011" ; // Function Call findMinimumOperations(A,B); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // JavaScript program for the // above approach // Function that finds the minimum // number of operations required such // that string A and B are the same function findMinimumOperations(a, b) { // Stores the count of steps var step = 0; // Stores the last index whose // bits are not same var last_index = 0; // Iterate until both string // are unequal while (a !== b) { // Check till end of string to // find rightmost unequals bit for ( var i = 0; i < a.length; i++) { // Update the last index if (a[i] !== b[i]) { last_index = i; } } // Flipping characters up // to the last index var ch = a.split( "" ); for ( var i = 0; i <= last_index; i++) { // Flip the bit if (ch[i] === "0" ) { ch[i] = "1" ; } else { ch[i] = "0" ; } } a = ch.join( "" ); // Increasing steps by one step++; } // Print the count of steps document.write(step); } // Driver Code // Given strings A and B var A = "101010" ; var B = "110011" ; // Function Call findMinimumOperations(A, B); // This code is contributed by rdtank </script> |
4
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us