Q3. Maximum Bitwise XOR After Rearrangement

📘 題目敘述

給你兩個長度為 n 的二進位字串 s 和 t。可以任意重排 t，s 保持不變，求可得到的最大 XOR 結果字串。

條件限制

• 1 <= n == s.length == t.length <= 2 * 10^5
• s[i]、t[i] 只會是 '0' 或 '1'

🧠 解題思路

要讓整體數值最大，就要從左到右盡量讓每一位 XOR 變成 1。

先統計 t 還剩多少個 0 與 1，再依序掃 s：

• s[i] == '0' 時優先放 1
• s[i] == '1' 時優先放 0

若理想 bit 用完，就放另一種 bit，該位就只能是 0。

所有變數

• dit：dit[0] 與 dit[1] 表示 t 剩餘的 0/1 數量
• ans：答案字串

🪜 主要流程步驟

1. 先統計 t 的 0 和 1

掃過 t 建立計數。

2. 從左到右掃 s，盡量做出 1

每個位置優先消耗能讓 XOR=1 的 bit，否則用剩餘 bit。

3. 回傳 ans

掃描完成後的 ans 就是最大 XOR 結果。

⏱️ 複雜度

• 時間複雜度：O(n)
• 空間複雜度：O(1)（不含輸出）

💻 程式碼實作

class Solution {
public:
    string maximumXor(string s, string t) {
        int dit[2] = {0};
        string ans = "";
        for (char a : t) {
            if (a == '0') {
                dit[0]++;
            } else {
                dit[1]++;
            }
        }
        for (char b : s) {
            if (b == '0') {
                if (dit[1] > 0) {
                    ans += '1';
                    dit[1]--;
                } else {
                    ans += '0';
                    dit[0]--;
                }
            } else {
                if (dit[0] > 0) {
                    ans += '1';
                    dit[0]--;
                } else {
                    ans += '0';
                    dit[1]--;
                }
            }
        }
        return ans;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-490/problems/maximum-bitwise-xor-after-rearrangement/