# Apply Bitwise Operations to Make Strings Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-bitwise-operations-to-make-strings-equal)
Canonical: https://scaleengineer.com/dsa/problems/apply-bitwise-operations-to-make-strings-equal
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** String
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## 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 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 = "**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:**

**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`.

# Approaches
## Full Scan and Count
This approach is based on the core observation about the bitwise operations. The key insight is that a string containing at least one '1' can be transformed into any other string that also contains at least one '1'. Conversely, a string of all '0's can never produce a '1', and a string with a '1' can never become all '0's. Therefore, the problem reduces to checking if both strings either contain at least one '1' or both are composed entirely of '0's. This approach determines this by counting all occurrences of '1' in both strings.
**Time:** O(N), where N is the length of the strings. We must iterate through both strings completely to count all the '1's. · **Space:** O(1), as we only use a few variables to store the counts, regardless of the input size.
**Pros:** The logic is straightforward and directly implements the derived condition.; It correctly solves the problem for all cases.
**Cons:** This approach is slightly suboptimal because it always scans the entire length of both strings, even if a '1' is found at the very beginning. It performs more work than necessary.
### Explanation
The logic hinges on the properties of the given bitwise operation: `s[i]` becomes `s[i] OR s[j]` and `s[j]` becomes `s[i] XOR s[j]`. Let's analyze the transitions for a pair of bits `(s[i], s[j])`:

*   `('0', '0') -> ('0', '0')`: No '1's can be created from only '0's.
*   `('0', '1') -> ('1', '1')`: A '1' can be used to turn a '0' into a '1'.
*   `('1', '0') -> ('1', '1')`: Same as above.
*   `('1', '1') -> ('1', '0')`: Two '1's can be used to turn one of them into a '0'.

From this, we can deduce:
1.  If a string `s` has no '1's (it's all '0's), it can never be transformed into a string with a '1'.
2.  If a string `s` has at least one '1', it can never be transformed into the all-'0's string. This is because any operation involving a '1' will result in at least one '1' in the output pair. You always retain at least one '1'.
3.  Furthermore, if a string `s` has at least one '1', it can be transformed into any other string `target` that also has at least one '1'. A '1' can act as a catalyst to change any other bit to '0' or '1'.

Therefore, a transformation is possible if and only if `s` and `target` have the same status regarding the presence of '1's. This approach verifies this by counting the total number of '1's in each string and then checking if both counts are zero or both are greater than zero.

```java
class Solution {
    public boolean makeStringsEqual(String s, String target) {
        int s_ones = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '1') {
                s_ones++;
            }
        }

        int t_ones = 0;
        for (int i = 0; i < target.length(); i++) {
            if (target.charAt(i) == '1') {
                t_ones++;
            }
        }

        boolean s_has_one = s_ones > 0;
        boolean target_has_one = t_ones > 0;

        return s_has_one == target_has_one;
    }
}
```
### Algorithm
- Initialize two counters, `s_ones` and `t_ones`, to zero.
- Iterate through the source string `s` from beginning to end. For each character that is '1', increment `s_ones`.
- Iterate through the target string `target` from beginning to end. For each character that is '1', increment `t_ones`.
- The condition for the strings to be convertible is `(s_ones > 0) == (t_ones > 0)`.
- Return the result of this boolean comparison.

## Optimized Presence Check with Early Exit
This approach builds on the same fundamental logic as the previous one: a transformation is possible if and only if both strings either contain a '1' or neither does. However, instead of counting all '1's, this method performs a more efficient check. It simply verifies the presence of at least one '1' and stops scanning as soon as one is found. This optimization can lead to significant performance improvements in cases where a '1' appears early in the strings.
**Time:** O(N) in the worst case, where N is the string length (e.g., when one or both strings are all '0's). However, the average and best-case time complexity is much better, approaching O(1) if '1's are found at or near the beginning of the strings. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Most efficient solution possible, as it stops searching as soon as the condition is met.; Achieves optimal time complexity with a better best-case and average-case performance than a full scan.; Very concise and readable, especially when using built-in string methods.
**Cons:** There are no significant disadvantages to this approach as it is optimal.
### Explanation
The underlying principle remains the same: the set of all binary strings is partitioned into two groups that cannot be reached from one another: the all-'0's string, and the set of all strings containing at least one '1'. Any string in the latter group can be transformed into any other string in the same group.

Therefore, the problem is equivalent to checking if `s` and `target` belong to the same group.

Instead of a full count, we can use a built-in function like `String.contains()` which is optimized to stop searching as soon as a match is found. This checks for the existence of a '1' without needing to traverse the entire string if a '1' is found near the beginning.

```java
class Solution {
    public boolean makeStringsEqual(String s, String target) {
        // The core logic is that if a string has at least one '1',
        // it can be transformed into any other string with at least one '1'.
        // A string with all '0's can only be equal to another all '0's string.
        // Therefore, we just need to check if the presence of '1's is the same in both strings.
        
        // String.contains() is efficient as it stops once the character is found.
        boolean s_has_one = s.contains("1");
        boolean target_has_one = target.contains("1");
        
        return s_has_one == target_has_one;
    }
}
```

This is the most concise and efficient way to implement the solution.
### Algorithm
- Check if the source string `s` contains the character '1'. This can be done with a loop that exits as soon as a '1' is found, or by using a built-in library function. Store the boolean result in `s_has_one`.
- Similarly, check if the target string `target` contains '1' and store the result in `target_has_one`.
- Return the value of `s_has_one == target_has_one`.

# Solutions
### Java

```java
class Solution {
public
  boolean makeStringsEqual(String s, String target) {
    return s.contains("1") == target.contains("1");
  }
}

```

### Python

```python
class Solution:
    def makeStringsEqual(
        self, s: str, target: str) -> bool: return ("1" in s) == ("1" in target)

```

### CPP

```cpp
class Solution {
public:
  bool makeStringsEqual(string s, string target) {
    auto a = count(s.begin(), s.end(), '1') > 0;
    auto b = count(target.begin(), target.end(), '1') > 0;
    return a == b;
  }
};

```