Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go
• TypeScript

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

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

• 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)
  
  

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

• 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('');
  }
  
  

All Problems

All Solutions