Minimum number of prefix flips required to convert a binary string to another

In this problem, we need to convert the first binary string to the second binary string by flipping its prefix. To get the minimum number of prefix flips, we need to iterate through the end of the strings, and if a non-matching character is found in both strings, we need to flip the prefix of the first string.

Problem Statement − We are given two different binary strings, called first and second. The two binary strings are equal in length, N. We need to convert the first string to the second string by flipping its prefix. Here, we need to calculate the total number of prefix flips required to convert one string to another. Flip means converting '0' to '1' and '1' to '0'.

Sample Examples

Input –  first = "001", second = "000"

Output – 2

Explanation

• First, we need to flip the prefix of length 3 for the first string, and the resultant string will be 110.

• After this we need to flip the prefix of length 2 and the resulting string will be 000, equal to the second string.

Input –  first = "10", second = "01"

Output – 1

Explanation

We require to flip the prefix of length 2, and the resultant string will be ‘01’, which is equal to the second string.

Input –  first = "11", second = "11"

Output – 0

Explanation

Since the two strings are equal, we don't need to do any flipping.

Approach 1

In this method, we iterate from the end of the string and if a non-matching character is found, we flip all the characters in the prefix of length 'I 1'. This is a simple way to solve the problem.

algorithm

• Step 1 - Define variable 'cnt' and initialize it to 0.

• Step 2 − Start traversing the string from the end using the loop.

• Step 3 − If first[i] and second[i] are not equal, we need to flip all the characters of the prefix whose length is equal to the I 1.

• Step 4 − Use the nest for loop to iterate through the prefix of length equal to I 1, and flip each character of it by executing the flipBits() function.

• Step 4.1 − We return '0' if the current character is '1' and '1' if the current character is '0' in the flipBits() function.

• Step 5 − Increase the value of the ‘cnt’ variable by 1 when we flip the prefix.

• Step 6 - Return the value of the 'cnt' variable.

Example

#include <bits/stdc++.h>
using namespace std;
char flipBits(char ch){
   // if the bit is '0', flip it to '1', else flip it to '0'.
   return (ch == '0') ? '1' : '0';
}
int minimumFlips(string first, string second, int n){
   // to store the count of flips
   int cnt = 0;
   
   // Traverse the string
   for (int i = n - 1; i >= 0; i--){
   
      // If first[i] is not equal to second[i]
      if (first[i] != second[i]){
      
         // flip the bits
         for (int j = 0; j <= i; j++){
            first[j] = flipBits(first[j]);
         }
         cnt++;
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Output

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Approach 2

In this approach, we will use the 'inverted' variable to track whether the current bit is flipped or not, rather than flipping each prefix bit every time. We also optimized the time complexity of the code in this approach.

algorithm

• Step 1 − Define the 'cnt' variable and initialize it with '0'. Also, define the 'inverted' variable and initialize it with a false value.

• Step 2 - Traverse the string starting from the end. If the first [i] and second [i] characters do not match, follow these steps.

• Step 2.1 − If the value of the 'inverted' is false, increase the value of the 'cnt' variable by 1, and change the value of the 'inverted' variable to true .

• Step 3 − If both characters match, and the value of the 'inverted' is true, we need to flip the bit again. So, increase the value of 'cnt' by 1 , and change the value of 'inverted' to false.

Example

Let’s debug the above algorithm by taking the example.

Input – first = ‘001’, second = ‘000’

• In the first step, the first [2] and the second [2] do not match, and the value of 'inverted' is false. Therefore, the value of 'cnt' will become 1 and 'inverted' will become true. Here, by changing the value of 'inverted' to true, we assume that we have virtually inverted the prefix.

• After that, the first[1] and second[1] match, but the value of the 'inverted' is true. So, the 'cnt' value will become 2, and the 'inverted' is false .

• Next, the first[0] and second[0] match, and the value of ‘inverted’ is false. So, we don’t need to perform any operation.

• Finally, it returns 'cnt', which has a value of 2.

#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of flips of prefixes required to convert the first binary string to the second
int minimumFlips(string first, string second, int N){

   // number of flips
   int cnt = 0;
   
   // to track whether the current bit is already flipped.
   // When we flip a bit 2 times, it becomes the same as the original bit.
   bool inverted = false;
   
   // Traverse the given string
   for (int i = N - 1; i >= 0; i--){
   
      // If A[i] is not equal to B[i]
      if (first[i] != second[i]){
      
         // If the current bit is not already flipped
         if (!inverted){
            cnt++; // Increase the count of flips
            inverted = true; // Invert all prefix bits
         }
      }
      else{
      
         // If A[i] is equal to B[i], but a current bit is flipped, we need to flip it again
         if (inverted){
         
            // Increase the count of flips
            cnt++;
            
            // Update inverted to false
            inverted = false;
         }
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Output

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Conclusion

We learned two methods to find the minimum number of prefix flips required to convert one string to another. The logic is to iterate through the string from the end and flip the prefix if we find a non-matching character.

We optimized the second piece of code in terms of time complexity by using the "inverted" variable to keep track of the inverted prefixes instead of inverting them like the first approach.

The above is the detailed content of Minimum number of prefix flips required to convert a binary string to another. For more information, please follow other related articles on the PHP Chinese website!