Apply Bitwise Operations to Make Strings Equal
MedPrompt
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
iandjwhere0 <= i, j < n. - Simultaneously, replace
s[i]with (s[i]ORs[j]) ands[j]with (s[i]XORs[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 <= 105sandtargetconsist of only the digits0and1.
Approaches
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize two counters,
s_onesandt_ones, to zero. - Iterate through the source string
sfrom beginning to end. For each character that is '1', increments_ones. - Iterate through the target string
targetfrom beginning to end. For each character that is '1', incrementt_ones. - The condition for the strings to be convertible is
(s_ones > 0) == (t_ones > 0). - Return the result of this boolean comparison.
Walkthrough
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:
- If a string
shas no '1's (it's all '0's), it can never be transformed into a string with a '1'. - If a string
shas 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'. - Furthermore, if a string
shas at least one '1', it can be transformed into any other stringtargetthat 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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Check if the source string
scontains 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 ins_has_one. - Similarly, check if the target string
targetcontains '1' and store the result intarget_has_one. - Return the value of
s_has_one == target_has_one.
Walkthrough
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.
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.
Complexity
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.
Trade-offs
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.
Solutions
Solution
class Solution {public boolean makeStringsEqual(String s, String target) { return s.contains("1") == target.contains("1"); }}class Solution: def makeStringsEqual( self, s: str, target: str) -> bool: return ("1" in s) == ("1" in target)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; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.