2546. Apply Bitwise Operations to Make Strings Equal

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 <= 105
• s and target consist of only the digits 0 and 1.

Solutions

Solution 1: Lateral Thinking

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)$.

1
2
3

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

1
2
3
4
5

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

1
2
3
4
5
6
7
8

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;
    }
};

1
2
3

func makeStringsEqual(s string, target string) bool {
	return strings.Contains(s, "1") == strings.Contains(target, "1")
}

1
2
3

function makeStringsEqual(s: string, target: string): boolean {
    return s.includes('1') === target.includes('1');
}

1
2
3
4
5

impl Solution {
    pub fn make_strings_equal(s: String, target: String) -> bool {
        s.contains('1') == target.contains('1')
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

bool makeStringsEqual(char* s, char* target) {
    int count = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '1') {
            count++;
            break;
        }
    }
    for (int i = 0; target[i]; i++) {
        if (target[i] == '1') {
            count++;
            break;
        }
    }
    return !(count & 1);
}