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

Python3JavaC++GoTypeScriptRustC

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

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

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

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

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

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

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

Comments