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:
i and j where 0 <= i, j < n.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.length2 <= n <= 105s and target consist of only the digits 0 and 1.Problem Overview: You are given two binary strings s and target. You can repeatedly choose two different indices and replace s[i] with either s[i] OR s[j] or s[i] XOR s[j]. The goal is to determine whether these operations can transform s into target.
Approach 1: Count Ones and Zeros (O(n) time, O(1) space)
Iterate through both strings and count the number of '1' characters. The key observation comes from how the allowed operations behave. OR can spread a 1 to other positions, while XOR can flip bits if another 1 exists in the string. Because of this, once a string contains at least one 1, you can propagate or flip bits to build any configuration that also contains a 1. However, if the string contains no 1, all operations keep it zero forever. The transformation is possible only when both strings either contain at least one 1 or both contain none. Counting provides a straightforward way to check this condition.
This method performs a single pass through each string, using constant memory. The counts themselves are not strictly required beyond determining whether a 1 exists, but they make the reasoning explicit and easy to verify.
Approach 2: Presence of Both Digits (O(n) time, O(1) space)
The optimal approach simplifies the previous idea even further. Instead of counting, check whether each string contains at least one '1'. The allowed operations create a useful invariant: you cannot generate the first 1 if the string starts with all zeros, and you cannot eliminate the final 1 once it exists. This means the existence of a 1 in the string never changes from zero to non‑zero or vice versa.
Compute hasOneS = s.contains('1') and hasOneT = target.contains('1'). If both values match, the transformation is possible. If one string has a 1 and the other does not, no sequence of operations can bridge that gap.
This solution uses a single linear scan and constant extra space. The reasoning relies on understanding how bitwise operations propagate bits, which makes it a good exercise when practicing bit manipulation and string processing problems.
Recommended for interviews: The presence-check approach is what most interviewers expect. It shows that you recognized the invariant created by the bitwise operations rather than simulating transformations. A counting version demonstrates the same idea but is slightly more verbose. The optimal insight—checking whether both strings share the same "contains 1" state—demonstrates strong reasoning about bitwise operations.
This approach is based on the idea that, to convert the string s to the target using the described operations, you need to either transform a '0' to a '1' or ensure both strings already match with respect to the position's bits. To achieve a target, the count of '1's in both strings must match, as the operations cannot increase or decrease the total count of '1's.
This C implementation iterates through both strings counting the number of '1's. It then checks if these counts are equal for s and target. If they are, it returns true; otherwise, it returns false.
Time Complexity: O(n) | Space Complexity: O(1)
The critical observation here is that the operations allow us to swap '0' to '1' and vice versa, provided both '1' and '0' exist in the string. It is possible to make the transformation if and only if both strings have at least one '1' and at least one '0', or they are already identical.
This C solution checks if the strings are already equal. If not, it checks if the string s contains both '1' and '0'. If both exist, a transformation is still possible, otherwise it is not.
Time Complexity: O(n) | Space Complexity: O(1)
We notice that 1 is actually a "tool" for number conversion. Therefore, as long as both strings either have 1 or neither have 1, we can make the two strings equal through operations.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Count Ones and Zeros | Time Complexity: O(n) | Space Complexity: O(1) |
| Approach 2: Presence of Both Digits | Time Complexity: O(n) | Space Complexity: O(1) |
| Lateral Thinking | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Count Ones and Zeros | O(n) | O(1) | Good for explaining the reasoning step‑by‑step by explicitly counting digits in both strings. |
| Presence of Both Digits | O(n) | O(1) | Best practical solution. Only checks whether each string contains at least one '1'. |
Apply Bitwise Operations to Make Strings Equal || Weekly Contest 329 || #Leetcode || C++ Solution • Code With U-DAY • 1,099 views views
Watch 9 more video solutions →Practice Apply Bitwise Operations to Make Strings Equal with our built-in code editor and test cases.
Practice on FleetCode