Apply Bitwise Operations to Make Strings Equal

MEDIUM

Description

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 = "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.length
2 <= n <= 10⁵
s and target consist of only the digits 0 and 1.

Approaches

Checkout 2 different approaches to solve Apply Bitwise Operations to Make Strings Equal. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 s has no '1's (it's all '0's), it can never be transformed into a string with a '1'.
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'.
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.

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 Analysis

Time Complexity: O(N), where N is the length of the strings. We must iterate through both strings completely to count all the '1's.Space Complexity: O(1), as we only use a few variables to store the counts, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Apply Bitwise Operations to Make Strings Equal. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Apply Bitwise Operations to Make Strings Equal

Patterns:

Bit Manipulation

Data Structures:

String

Companies:

Sprinklr |