Make binary strings equal by repeatedly replacing the second bit

In this problem, we need to convert bin1 string to bin2 string by replacing the second character of bin1 string with the first and second characters The minimum or maximum value in , and the first character is deleted.

Since we need to delete the first character, we need to ensure that the last len2 − 1 characters in the two strings are the same. Additionally, we need to make sure that we can get the first character of the second string by performing the given operation on the starting character of the bin1 string.

Problem Statement - We are given bin1 and bin2 binary strings of length len1 and len2 respectively. We need to check if we can convert bin1 string to bin2 string by doing the following.

• Update the second character of the bin1 string using the minimum or maximum value of the first and second characters of the bin1 string.

• Remove the first character of the bin1 string, and the string size will be reduced by 1 each time.

Example

enter

bin1 = "0101011"; bin2 = "011";

Output

Yes

Instructions- We can do the following to convert bin1 string to bin2 string.

• We can replace the second character with min(0,1) and delete the first character. Therefore, the string becomes 001011.

• We perform the same operation again and the string becomes 01011.

• In the next few operations, the string becomes 0011 and 011 respectively.

enter

bin1 = "1110"; bin2 = "1110";

Output

Yes

Explanation - The given strings are already the same.

enter

bin1 = "101101"; bin2 = "1110";

Output

No

Explanation - We cannot convert bin1 string to bin2 string by performing the given operation.

method 1

If the length of bin1 string is smaller, we cannot convert it to bin2 string.

In other cases, the last len2 − 1 characters of the bin1 string remain unchanged because we do not perform any operation on it. Therefore, the last len2 − 1 characters in both strings should be the same.

In addition, if the first character of the bin2 string is '0', we should perform min() operation on the starting character of the bin1 string, and it should contain at least one '0'.

If the first character in the bin2 string is '1', we should perform max() operation on the starting character of the bin2 string, and it should contain at least one '1'.

algorithm

Step 1 - If the length of bin1 is less than the length of bin2 string, return false.

Step 2 - Traverse the bin2 string starting from the second position.

Step 3 - If bin2[p] is not equal to bin1[p len1 - len2], return false because the last len2 -1 characters are not the same.

Step 4 - Traverse the first len1 - len2 1 character and check whether it contains the bin2[0] character. If yes, return true.

Step 5 - Return false at the end of the function.

Example

#include <bits/stdc++.h>
using namespace std;

bool convertAtoB(string bin1, string bin2) {
    int len1 = bin1.size(), len2 = bin2.size();
    // When length 1 is less than length 2
    if (len1 < len2) {
        return false;
    }
    // Check whether substring bin1[p + len1 - len2]... bin1[len1] and bin2[1]... bin2[len2]
    for (int p = 1; p < len2; p++) {
        if (bin1[p + len1 - len2] != bin2[p]) {
            return false;
        }
    }
    // Check whether substring bin1[0... len1 - len2 - 1] contains bin2[0]
    for (int p = 0; p < len1 - len2 + 1; p++) {
        if (bin1[p] == bin2[0]) {
            return true;
        }
    }
    return false;
}
int main() {
    string bin1 = "0101011";
    string bin2 = "011";
    bool res = convertAtoB(bin1, bin2);
    if (res == true) {
        cout << "YES, It is possible to convert bin1 to bin2.";
    } else {
        cout << "NO, It is not possible to convert bin1 to bin2.";
    }
}

Output

YES, It is possible to convert bin1 to bin2.

Time complexity - O(N) to match string characters.

Space complexity - O(1), since we don't use any dynamic space.

We learned to convert the first binary string to the second binary string by following the given operation. A programmer might try to check if one string can be converted to another by replacing the last character with the minimum or maximum value of the last and last second characters and removing the last character.

The above is the detailed content of Make binary strings equal by repeatedly replacing the second bit. For more information, please follow other related articles on the PHP Chinese website!