Maximum bitwise xor after rearrangement

String Greedy Bit Manipulation

71.0% acceptance

Mar 15, 2026

You are given two binary strings s and t of length n. You may rearrange t in any order, but s must remain unchanged. Return binary string of length n representing max XOR of s and rearranged t.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_xor(s: String, t: String) -> String {
    let ones_in_t = t.bytes().filter(|&b| b == b'1').count();
    let zeros_in_t = t.len() - ones_in_t;
    let s_bytes: Vec<u8> = s.bytes().collect();

    let mut remaining_ones = ones_in_t;
    let mut remaining_zeros = zeros_in_t;
    let mut result = Vec::with_capacity(s.len());

    for &sb in &s_bytes {
      if sb == b'0' {
        if remaining_ones > 0 {
          remaining_ones -= 1;
          result.push(b'1');
        } else {
          remaining_zeros -= 1;
          result.push(b'0');
        }
      } else {
        if remaining_zeros > 0 {
          remaining_zeros -= 1;
          result.push(b'1');
        } else {
          remaining_ones -= 1;
          result.push(b'0');
        }
      }
    }

    String::from_utf8(result).unwrap()
  }
}