Minimum prefixes required to be flipped to convert a Binary String to another
Given two binary strings A and B of length N, the task is to convert the string from A to string B by repeatedly flipping all the bits of a prefix of A, i.e. convert all the 0s in the prefix to 1s and vice-versa and print the minimum number of prefix flips required and the length of respective prefixes.
Input: A = “001”, B = “000”
Flipping the prefix “001” modifies the string to “110”.
Flipping the prefix “11” modifies the string to “000”.
Input: A = “1000”, B = “1011”
Flipping the prefix “1000” modifies the string to “0111”.
Flipping the prefix “01” modifies the string to “1011”.
Naive Approach: The simplest approach is to traverse the string A in reverse and for every ith character obtained such that A[i] is not equal to B[i], flip the characters present in A from indices [0, i] and increment the number of operations by 1. After complete traversal of the string, print the count of operations and the prefix length chosen in each operation.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to fix one bit at a time by traversing the string A in reverse. Maintain a boolean variable, say invert, initially set to false, to denote whether the current bits in A are flipped or not. While traversing, perform the following:
- If the iᵗʰ bit in A is not equal to the iᵗʰ bit in B and invert is false, then increment the count of operations and set invert to true.
- Otherwise, if the iᵗʰ bit in A is equal to the iᵗʰ bit in B and invert is true, then increment the count of operations and set invert to false.
Follow the steps below to solve the problem:
- Initialize a boolean variable, say invert as false, to denote whether the bits in A are flipped or not.
- Initialize an empty array, say res, to store the prefix length in each operation.
- Iterate in the range [N – 1, 0] using the variable i and perform the following steps:
- If A[i] != B[i] and invert is false, then the current bit is required to be flipped. Therefore. insert (i + 1) into the array res and update invert to true.
- Otherwise, check if A[i] == B[i] and invert is true, then insert (i + 1) to res, and update invert to false.
- Print the size of the array res as the number of operations required to make the two strings equal.
- Then, print the values stored in res to denote the prefix length in each operation.
Below is the implementation of the above approach:
2 3 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.