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:
i and j where 0 <= i, j < n.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.length2 <= n <= 105s and target consist of only the digits 0 and 1.class Solution {
public:
bool makeStringsEqual(string s, string target) {
int s0=0, s1=0, t0=0, t1=0;
for(auto c: s)
c=='0'?s0++:s1++;
for(auto c: target)
c=='0'?t0++:t1++;
// 0 1 ---> 1 1
// 0 0 ---> 0 0 (useless)
// 1 1 ---> 1 0
if(t1==s1) return true; // posn doesnt matter since, using combination 1st and 3rd successively posns can be swapped
return s1&&t1; // atleast one 1 guarantees change of all the other required bits (Note that one 1 still remains unchanged finally)
}
};