Skip to content

3849. Maximum Bitwise XOR After Rearrangement

Description

You are given two binary strings s and t​​​​​​​, each of length n.

You may rearrange the characters of t in any order, but s must remain unchanged.

Return a binary string of length n representing the maximum integer value obtainable by taking the bitwise XOR of s and rearranged t.

Β 

Example 1:

Input: s = "101", t = "011"

Output: "110"

Explanation:

  • One optimal rearrangement of t is "011".
  • The bitwise XOR of s and rearranged t is "101" XOR "011" = "110", which is the maximum possible.

Example 2:

Input: s = "0110", t = "1110"

Output: "1101"

Explanation:

  • One optimal rearrangement of t is "1011".
  • The bitwise XOR of s and rearranged t is "0110" XOR "1011" = "1101", which is the maximum possible.

Example 3:

Input: s = "0101", t = "1001"

Output: "1111"

Explanation:

  • One optimal rearrangement of t is "1010".
  • The bitwise XOR of s and rearranged t is "0101" XOR "1010" = "1111", which is the maximum possible.

Β 

Constraints:

  • 1 <= n == s.length == t.length <= 2 * 105
  • s[i] and t[i] are either '0' or '1'.

Solutions

Solution 1: Greedy

We use an array \(\textit{cnt}\) of length \(2\) to count the number of character '0' and character '1' in string \(t\).

Then we iterate through string \(s\). For each character \(s[i]\), we want to find a character in string \(t\) that is different from \(s[i]\) to perform the XOR operation, in order to get a larger result. If we find such a character, we set the \(i\)-th bit of the answer to '1' and decrement the count of that character by one; otherwise, we can only use a character that is the same as \(s[i]\) for the XOR operation, the \(i\)-th bit of the answer remains '0', and we decrement the count of that character by one. Finally, we return the answer.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maximumXor(self, s: str, t: str) -> str:
        cnt = [0, 0]
        for c in t:
            cnt[int(c)] += 1
        ans = ['0'] * len(s)
        for i, c in enumerate(s):
            x = int(c)
            if cnt[x ^ 1]:
                cnt[x ^ 1] -= 1
                ans[i] = '1'
            else:
                cnt[x] -= 1
        return ''.join(ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String maximumXor(String s, String t) {
        int[] cnt = new int[2];
        for (char c : t.toCharArray()) {
            cnt[c - '0']++;
        }

        char[] ans = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            int x = s.charAt(i) - '0';
            if (cnt[x ^ 1] > 0) {
                cnt[x ^ 1]--;
                ans[i] = '1';
            } else {
                cnt[x]--;
                ans[i] = '0';
            }
        }

        return new String(ans);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string maximumXor(string s, string t) {
        int cnt[2]{};
        for (char c : t) {
            cnt[c - '0']++;
        }

        string ans(s.size(), '0');
        for (int i = 0; i < s.size(); i++) {
            int x = s[i] - '0';
            if (cnt[x ^ 1] > 0) {
                cnt[x ^ 1]--;
                ans[i] = '1';
            } else {
                cnt[x]--;
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func maximumXor(s string, t string) string {
    cnt := make([]int, 2)
    for _, c := range t {
        cnt[c-'0']++
    }

    ans := make([]byte, len(s))
    for i := 0; i < len(s); i++ {
        x := s[i] - '0'
        if cnt[x^1] > 0 {
            cnt[x^1]--
            ans[i] = '1'
        } else {
            cnt[x]--
            ans[i] = '0'
        }
    }

    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function maximumXor(s: string, t: string): string {
    const cnt = [0, 0];

    for (const c of t) {
        cnt[Number(c)]++;
    }

    const ans: string[] = new Array(s.length).fill('0');

    for (let i = 0; i < s.length; i++) {
        const x = Number(s[i]);
        if (cnt[x ^ 1] > 0) {
            cnt[x ^ 1]--;
            ans[i] = '1';
        } else {
            cnt[x]--;
        }
    }

    return ans.join('');
}

Comments