2546

2546. Apply Bitwise Operations to Make Strings Equal (Medium)

You are given two 0-indexed binary strings s and target of the same length n. You can do the following operation on s any number of times:

• Choose two different indices i and j where 0 <= i, j < n.
• Simultaneously, replace s[i] with (s[i] OR s[j]) and s[j] with (s[i] XOR s[j]).

For example, if s = "0110", you can choose i = 0 and j = 2, then simultaneously replace s[0] with (s[0] OR s[2] = 0 OR 1 = 1), and s[2] with (s[0] XOR s[2] = 0 XOR 1 = 1), so we will have s = "1110".

Return true if you can make the string s equal to target, or false otherwise.

 

Example 1:

Input: s = "1010", target = "0110"
Output: true
Explanation: We can do the following operations:
- Choose i = 2 and j = 0. We have now s = "0010".
- Choose i = 2 and j = 1. We have now s = "0110".
Since we can make s equal to target, we return true.

Example 2:

Input: s = "11", target = "00"
Output: false
Explanation: It is not possible to make s equal to target with any number of operations.

 

Constraints:

• n == s.length == target.length
• 2 <= n <= 105
• s and target consist of only the digits 0 and 1.

Companies: Sprinklr

Related Topics:
String, Bit Manipulation

Similar Questions:

• Minimum One Bit Operations to Make Integers Zero (Hard)

Solution 1.

    or  xor
0 0 0   0
0 1 1   1
1 1 1   0

We can see:

• for 00 pairs, we can't change them.
• for 01 or 10 pairs, we can change them to 11.
• for 11 pairs, we can change them to 01 or 10.

So, we just need to cound the number of 1s in both strings. If they are both zeros or both non-zeros, we return true.

// OJ: https://leetcode.com/problems/apply-bitwise-operations-to-make-strings-equal
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    bool makeStringsEqual(string s, string target) {
        int a = 0, b = 0;
        for (char c : s) a += c == '1';
        for (char c : target) b += c == '1';
        return (a == 0 && b == 0) || (a && b);
    }
};

Or

// OJ: https://leetcode.com/problems/apply-bitwise-operations-to-make-strings-equal
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    bool makeStringsEqual(string s, string target) {
        return (s.find('1') != string::npos) == (target.find('1') != string::npos);
    }
};