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

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。

一、题目核心规则梳理

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

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

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

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

逐位演示样例 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. 时间复杂度 O(n)

n 为字符串长度：

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

2. 额外空间复杂度 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
}
}
return string(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;
return 0;
}