Problem

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 strings equal totarget , orfalse otherwise.

Examples

Example 1

1
2
3
4
5
6

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

Example 2

1
2
3

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 <= 10^5
  • s and target consist of only the digits 0 and 1.

Solution

Method 1 – Bit Count Parity

Intuition

The key insight is that the allowed operation lets us freely move and combine 1s in the string, but we can never create a 1 if there wasn’t one to begin with. Thus, if both s and target have at least one 1, we can always transform s into target. If both are all 0s, they’re already equal. If one has 1 and the other doesn’t, it’s impossible.

Approach

  1. Count the number of 1s in both s and target.
  2. If both have at least one 1, return true.
  3. If both have all 0s, return true only if s == target.
  4. Otherwise, return false.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
  bool makeStringsEqual(string s, string target) {
    bool has1s = s.find('1') != string::npos;
    bool has1t = target.find('1') != string::npos;
    return (has1s == has1t);
  }
};
1
2
3
4
5
6
7

class Solution {
  public boolean makeStringsEqual(String s, String target) {
    boolean has1s = s.indexOf('1') != -1;
    boolean has1t = target.indexOf('1') != -1;
    return has1s == has1t;
  }
}
1
2
3
4
5

class Solution:
  def makeStringsEqual(self, s: str, target: str) -> bool:
    has1s: bool = '1' in s
    has1t: bool = '1' in target
    return has1s == has1t

Complexity

  • ⏰ Time complexity: O(n) (where n is the length of the strings, for scanning for ‘1’)
  • 🧺 Space complexity: O(1) (constant extra space)