Apply Bitwise Operations to Make Strings Equal - Video Solutions

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.