3849. 重新排列后的最大按位异或

Medium

题目描述

给你两个长度为 n 的二进制字符串 s 和 t。

你可以将 t 的字符按任意顺序重新排列，但 s 必须保持不变。

返回一个长度为 n 的二进制字符串，表示 s 和重新排列的 t 进行按位异或运算后能得到的最大整数值。

示例 1：

输入：s = "101", t = "011"
输出："110"
解释：
t 的一个最优重新排列是 "011"。
s 和重新排列的 t 的按位异或运算结果是 "101" XOR "011" = "110"，这是可能的最大值。

示例 2：

输入：s = "0110", t = "1110"
输出："1101"
解释：
t 的一个最优重新排列是 "1011"。
s 和重新排列的 t 的按位异或运算结果是 "0110" XOR "1011" = "1101"，这是可能的最大值。

示例 3：

输入：s = "0101", t = "1001"
输出："1111"
解释：
t 的一个最优重新排列是 "1010"。
s 和重新排列的 t 的按位异或运算结果是 "0101" XOR "1010" = "1111"，这是可能的最大值。

提示：

1 <= n == s.length == t.length <= 2 * 10^5
s[i] 和 t[i] 都是 '0' 或 '1'

解题思路

这道题的核心思路是贪心算法配合位运算的性质。

基本观察：

XOR运算的特点：相同位得0，不同位得1
要使XOR结果最大，我们希望尽可能多的位为1
从左到右（高位到低位），每一位的权重递减，所以优先让高位为1

贪心策略：

统计字符串t中'0’和'1’的个数
从左到右遍历字符串s的每一位：
- 如果s[i] = ‘0’，优先匹配t中的'1’，这样XOR结果为1
- 如果s[i] = ‘1’，优先匹配t中的'0’，这样XOR结果为1
- 如果无法匹配到相反的字符，只能匹配相同字符，XOR结果为0

算法步骤：

遍历t，统计'0’和'1’的数量
初始化结果字符串
从左到右处理s的每个字符，贪心地选择t中的字符来最大化当前位的XOR值
更新t中对应字符的剩余数量

时间复杂度O(n)，空间复杂度O(1)，这是最优解法。

代码实现

class Solution {
public:
    string maximumXor(string s, string t) {
        int count0 = 0, count1 = 0;
        // 统计t中'0'和'1'的个数
        for (char c : t) {
            if (c == '0') count0++;
            else count1++;
        }
        
        string result = "";
        for (char c : s) {
            if (c == '0') {
                // s[i]='0'，优先选择t中的'1'使XOR为1
                if (count1 > 0) {
                    result += '1';
                    count1--;
                } else {
                    result += '0';
                    count0--;
                }
            } else {
                // s[i]='1'，优先选择t中的'0'使XOR为1
                if (count0 > 0) {
                    result += '1';
                    count0--;
                } else {
                    result += '0';
                    count1--;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def maximumXor(self, s: str, t: str) -> str:
        # 统计t中'0'和'1'的个数
        count0 = t.count('0')
        count1 = t.count('1')
        
        result = []
        for c in s:
            if c == '0':
                # s[i]='0'，优先选择t中的'1'使XOR为1
                if count1 > 0:
                    result.append('1')
                    count1 -= 1
                else:
                    result.append('0')
                    count0 -= 1
            else:
                # s[i]='1'，优先选择t中的'0'使XOR为1
                if count0 > 0:
                    result.append('1')
                    count0 -= 1
                else:
                    result.append('0')
                    count1 -= 1
        
        return ''.join(result)

public class Solution {
    public string MaximumXor(string s, string t) {
        int count0 = 0, count1 = 0;
        // 统计t中'0'和'1'的个数
        foreach (char c in t) {
            if (c == '0') count0++;
            else count1++;
        }
        
        StringBuilder result = new StringBuilder();
        foreach (char c in s) {
            if (c == '0') {
                // s[i]='0'，优先选择t中的'1'使XOR为1
                if (count1 > 0) {
                    result.Append('1');
                    count1--;
                } else {
                    result.Append('0');
                    count0--;
                }
            } else {
                // s[i]='1'，优先选择t中的'0'使XOR为1
                if (count0 > 0) {
                    result.Append('1');
                    count0--;
                } else {
                    result.Append('0');
                    count1--;
                }
            }
        }
        
        return result.ToString();
    }
}

var maximumXor = function(s, t) {
    let count0 = 0, count1 = 0;
    for (let char of t) {
        if (char === '0') count0++;
        else count1++;
    }
    
    let result = '';
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '0') {
            if (count1 > 0) {
                result += '1';
                count1--;
            } else {
                result += '0';
                count0--;
            }
        } else {
            if (count0 > 0) {
                result += '1';
                count0--;
            } else {
                result += '0';
                count1--;
            }
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n)	需要遍历字符串t统计字符数量，然后遍历字符串s构造结果
空间复杂度	O(1)	只使用常量级别的额外空间存储计数器，结果字符串不计入空间复杂度

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析