Skip to content

Latest commit

 

History

History
84 lines (75 loc) · 3.72 KB

README.md

File metadata and controls

84 lines (75 loc) · 3.72 KB

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:

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);
    }
};