2026-06-20：重新排列后的最大按位异或值。用go语言，给定两个长度都为 n 的二进制字符串 s 和 t。 你可以把 t 的字符任意顺序重排，但 s

2026-06-20：重新排列后的最大按位异或值。用go语言，给定两个长度都为 n 的二进制字符串 s 和 t。

你可以把 t 的字符任意顺序重排，但 s 不能改动。

然后把 s 和重排后的 t 按位做异或运算，得到一个新的二进制串。

你的任务是：在所有可能的重排方式中，找出使这个异或结果对应的“二进制整数值”最大的那一种，并返回对应的异或结果字符串。

1 <= n == s.length == t.length <= 200000。

s[i] 和 t[i] 不是 '0' 就是 '1'。

输入: s = "101", t = "011"。

输出: "110"。

解释:

t 的一个最佳重新排列方式是 "011"。

s 与重新排列后的 t 进行按位异或的结果是 "101" XOR "011" = "110"，这是可能的最大值。

题目来自力扣3849。

一、题目核心规则梳理

1. 1. 输入两个等长二进制字符串 s、t，长度均为 n；
2. 2. s 顺序固定，仅能对 t 的 0、1 字符自由重排；
3. 3. 重排后的 t 和 s 逐位异或：s[i] XOR t_new[i]，每一位结果规则：
   • • 0 XOR 1 = 1，1 XOR 0 = 1；
   • • 0 XOR 0 = 0，1 XOR 1 = 0；
4. 4. 二进制数值大小规则：高位优先，越靠左的位为1，整体数值越大；因此贪心策略：从左到右，每一位优先构造出异或结果1，实在无法构造再填0；
5. 5. 输出最终异或得到的二进制字符串。

二、算法完整分步执行流程（以样例 s="101"，t="011" 举例）

步骤1：统计 t 中原始 0、1 的总数量

1. 1. 遍历 t 字符串，统计字符 '0' 的总数 cnt0；
2. 2. t 总长度减去 cnt0 得到 cnt1（t 中 '1' 的总数）；
3. 3. 用数组 left = [剩余0数量, 剩余1数量] 保存 t 还未使用的 0、1，初始值为统计出来的 cnt0、cnt1。 样例 t="011"：

• • cnt0 = 1，cnt1 = 2，初始 left = [1, 2]。

步骤2：将 s 转为字节切片，方便逐位修改结果

直接把 s 复制到字节切片 ans，后续逐位确定每一位异或输出，最终转字符串返回； 样例 ans 初始为 ['1','0','1']。

步骤3：从左向右遍历 s 的每一位（贪心构造最大二进制）

遍历每一个下标 i，取出当前 s 的本位数字 x（0 或 1），目标优先让当前异或结果等于 1：

核心逻辑：要得到异或1，必须匹配与 x 相反的数字（x ^ 1）

• • 若当前 s 位是 0：想要异或出1，需要从剩余t中拿一个1；
• • 若当前 s 位是 1：想要异或出1，需要从剩余t中拿一个0； 对应代码中 x ^ 1：和 x 相反的数字（0变1，1变0）。

分两种分支处理每一位：

分支A：剩余t里还有相反数字（left[x^1] > 0）

1. 1. 消耗一个相反数字：left[x^1] -= 1；
2. 2. 本位异或结果填 '1'，存入 ans[i]；

分支B：没有相反数字，只能取和x相同的数字

1. 1. 消耗一个相同数字：left[x] -= 1；
2. 2. 本位异或结果只能是 '0'，存入 ans[i]。

逐位演示样例 s="101"，left=[1,2]

第1位 i=0，s字符='1'，x=1：

• • 需要相反数字 x^1=0，left[0]=1 > 0；
• • left[0] 减1 → left=[0,2]；
• • ans[0] = '1'；当前ans：['1','0','1']

第2位 i=1，s字符='0'，x=0：

• • 需要相反数字 x^1=1，left[1]=2 > 0；
• • left[1] 减1 → left=[0,1]；
• • ans[1] = '1'；当前ans：['1','1','1']

第3位 i=2，s字符='1'，x=1：

• • 需要相反数字 x^1=0，left[0]=0，无剩余0；
• • 只能取相同数字1，left[1] 减1 → left=[0,0]；
• • ans[2] = '0'；最终ans：['1','1','0']

步骤4：遍历全部字符完成后，将字节切片 ans 转为字符串返回

样例最终得到字符串 "110"，和题目输出一致。

三、整体流程总结

1. 1. 计数阶段：仅统计 t 里0、1的总量，O(n)；
2. 2. 贪心构造阶段：从左到右遍历 s 每一位，每一步只做常数次判断与减法，O(n)；
3. 3. 结果转换：字节切片转字符串，O(n)； 全程没有嵌套循环、排序、复杂运算，纯线性遍历。

四、复杂度分析

1. 时间复杂度 O(n)

n 为字符串长度：

• • 统计t中0的数量：一次遍历 t，O(n)；
• • 遍历s逐位生成结果：一次遍历 s，O(n)； 所有操作均为线性单次遍历，无嵌套循环，总时间复杂度：O(n)。

2. 额外空间复杂度 O(n)

额外开辟的内存：

1. 1. 长度为n的字节切片 ans，用来存储输出结果，必须占用；
2. 2. 定长数组 left=[2]int，固定常数空间 O(1)； 不计输入字符串本身占用的空间，仅算算法新增空间：O(n)。

补充说明：如果题目允许直接复用输入内存，仅常数空间；但代码中新建了独立的字节切片存储答案，因此额外空间由结果数组主导，为线性O(n)。

Go完整代码如下：

.

package main

import (
    "fmt"
    "strings"
)

func maximumXor(s, t string)string {
    cnt0 := strings.Count(t, "0")
    left := [2]int{cnt0, len(t) - cnt0} // t 中剩余的 0 和 1 的个数

    ans := []byte(s)
    for i, ch := range ans {
        x := int(ch - '0')
        // 如果 x 是 0，那就看还有没有剩下的 1
        // 如果 x 是 1，那就看还有没有剩下的 0
        if left[x^1] > 0 {
            left[x^1]--
            ans[i] = '1'// x ^ (x^1) = 1
        } else { // 只能让两个相同的数异或
            left[x]--
            ans[i] = '0'// x ^ x = 0
        }
    }
    returnstring(ans)
}

func main() {
    s := "101"
    t := "011"
    result := maximumXor(s, t)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

.

# -*-coding:utf-8-*-

def maximum_xor(s: str, t: str) -> str:
    cnt0 = t.count("0")
    left = [cnt0, len(t) - cnt0]  # t 中剩余的 0 和 1 的个数
    
    ans = list(s)
    for i, ch in enumerate(ans):
        x = int(ch)
        # 如果 x 是 0，那就看还有没有剩下的 1
        # 如果 x 是 1，那就看还有没有剩下的 0
        if left[x ^ 1] > 0:
            left[x ^ 1] -= 1
            ans[i] = '1'  # x ^ (x^1) = 1
        else:  # 只能让两个相同的数异或
            left[x] -= 1
            ans[i] = '0'  # x ^ x = 0
    
    return''.join(ans)


if __name__ == "__main__":
    s = "101"
    t = "011"
    result = maximum_xor(s, t)
    print(result)

在这里插入图片描述

C++完整代码如下：

.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string maximumXor(string s, string t) {
    int cnt0 = count(t.begin(), t.end(), '0');
    int left[2] = {cnt0, (int)t.length() - cnt0}; // t 中剩余的 0 和 1 的个数

    string ans = s;
    for (int i = 0; i < (int)ans.length(); i++) {
        int x = ans[i] - '0';
        // 如果 x 是 0，那就看还有没有剩下的 1
        // 如果 x 是 1，那就看还有没有剩下的 0
        if (left[x ^ 1] > 0) {
            left[x ^ 1]--;
            ans[i] = '1'; // x ^ (x^1) = 1
        } else { // 只能让两个相同的数异或
            left[x]--;
            ans[i] = '0'; // x ^ x = 0
        }
    }
    return ans;
}

int main() {
    string s = "101";
    string t = "011";
    string result = maximumXor(s, t);
    cout << result << endl;
    return0;
}

在这里插入图片描述