Makes the given binary strings equal by repeatedly replacing two consecutive 0's with a single 1

In any programming language, a binary string is a collection of characters 0 and 1. At each stage, the binary string follows the approach that the string can only contain these two characters.

Characters in a continuous string refer to characters whose index difference is 1. Let us consider two indices, i and j, they are said to be continuous if |j-i| = 1.

In C, if two strings are equivalent, it means:

• The corresponding characters in the two strings are the same.

• The lengths of the strings are equal, and the characters at the corresponding indexes overlap.

Some examples to illustrate the problem statement are as follows -

ExampleExample

str1 - "10001"

str2 - "101"

solution-

str1 cannot be converted to str2 because in the process of converting str1 to create the equivalent string str2, we will get str1 as "1011" and str2 as "101".

Example 2 - Let us consider the following input −

str1 - "001"

str2 - "11"

solution-

str1 can be converted to str2 by changing the first two zeros to a 1.

Using character matching and string traversal in C can solve the following problems.

algorithm

• Step 1 - Two pointers i and j are used to simultaneously iterate the strings s1 and s2 respectively.

• Step 2 - If the characters at both indices match, we increment the i and j pointers.

• Step 3 − If the characters are not equal, we check if the character at the i-th and (i 1)th index is '0', and the character at the j-th index Whether it is '1'.

• Step 4 - If such a situation exists, conversion can be performed. The i pointer is incremented by two positions and j is incremented by one index position because both zeros are converted to ones.

• Step 5 - If the characters are not equal and the above situation does not exist, the conversion cannot be performed.

• Step 6 − If both pointers i and j successfully reach the end position, s1 can be converted to s2.

Example

The following code snippet takes two binary strings as input and checks whether the two strings can be equivalent by simple character replacement based on specified conditions

//including the required libraries
#include <bits/stdc++.h>
using namespace std;

//convert consecutive 0's to 1
bool convertBinary(string s1, string s2){

   //fetching the lengths of both the strings
   int len1 = s1.length();
   int len2 = s2.length();
   string temp ="";

   //maintaining counters of both the strings
   int i = 0, j = 0;

   //iterating over both the strings simultaneously
   while (i < len1 && j < len2) {

      //if both the characters are equivalent in nature
      //skip to next character
      if (s1[i] == s2[j]) {
         temp+=s1[i];

         //incrementing both pointers
         i++;
         j++;
      }

      // if both characters differ
      else {

         // checking if '00' of s1 can be converted to '1' of s2
         if(s2[j]=='1' && s1[i]=='0'){

            //checking if i+1th index exists and is equivalent to 0
            if(i+1 < len1 && s1[i+1]=='0'){

               //conversion is possible
               //skip two 0's of s1 since converted to 1 in s2
               temp+='1';
               i += 2;
               j++;
            } else {
               return false;
            }
         }

         // If not possible to combine
         else {
            return false;
         }
      }
   }
   cout<<"Entered string2 "<<s2<<"\n";
   cout<<"Converted string1 "<<temp<<"\n";

   //check if both the strings are returned to end position
   if (i == len1 && j == len2)
      return true;
      return false;
}

// calling the conversion rate
int main(){
   string str1 = "100100";
   string str2 = "1111";

   //capturing result
   cout<<"Entered string1 "<<str1<<"\n";
   bool res = convertBinary(str1, str2);
   if (res)
      cout << "First string can be converted to second";
   else
      cout << "First string can't be converted to second";
   return 0;
}

Output

Entered string1 100100
Entered string2 1111
Converted string1 1111
First string can be converted to second

in conclusion

Since this method can effectively compare the input string character by character, the time complexity is O(min(string length)). String traversal is an important aspect of solving string problems.

The above is the detailed content of Makes the given binary strings equal by repeatedly replacing two consecutive 0's with a single 1. For more information, please follow other related articles on the PHP Chinese website!