Maximum Binary XOR After Rearranging One String
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given equal-length binary strings `s` and `t`. You may rearrange the characters of `t` arbitrarily, but `s` must stay in its original order.
Return the length-`n` binary string representing the largest integer obtainable as the bitwise XOR of `s` and a rearrangement of `t`. Preserve all `n` output positions, including leading zeros.
```cpp
class Solution {
public:
string maximumXor(string s, string t);
};
```
### Examples
**Example 1:**
```text
Input: s = "1100", t = "1000"
Output: "1110"
Explanation: Rearrange t as "0010". Then "1100" XOR "0010" = "1110", the greatest attainable result.
```
**Example 2:**
```text
Input: s = "111", t = "111"
Output: "000"
Explanation: Rearranging t cannot change it. The XOR is zero, represented with all three required output positions.
```
### Constraints
- `1 <= s.length == t.length <= 200000`.
- Both strings contain only `0` and `1`.
### Clarifying Questions
- May both strings be rearranged? No; only `t` may be rearranged.
- Must the counts of zeros and ones in `t` be preserved? Yes.
- Is the rearranged `t` returned? No; return the XOR result.
- Can leading zeros be dropped from the output? No; its length must remain `n`.
### What a Strong Answer Covers
- The allowed rearrangement and the fixed order of `s`.
- Preserving the full bit multiset of `t` and the output length.
- A feasible result and proof of its maximum numeric value.
- One-character and all-equal strings, numeric representation, and full-size resource bounds.
### Follow-up Questions
- What extra output would be needed to return a witnessing rearrangement too?
- How would allowing changes to both input strings alter the permitted choices?
```hint Use bit counts to prioritize significant output positions
Count zeros and ones in t. Scan s from left to right, using an available opposite bit to produce XOR one whenever possible. If that bit is exhausted, use a same-valued bit and produce zero. Compare an earlier one with any possible gain in less significant positions.
```
Overview: Maximize a binary XOR by rearranging only the second string. Covers exact bit counts, leading zeros, large outputs, proof, and a C++ solution.