Maximum Bitwise XOR After Rearrangement - Solution & Explanation

Problem Overview: You are given binary strings and allowed to rearrange their characters before computing the bitwise XOR. The goal is to maximize the resulting XOR value. Since XOR produces 1 when two bits differ, the optimal strategy focuses on creating as many mismatched bit positions as possible.

Approach 1: Brute Force Rearrangement (Factorial Time, Exponential Space)

The naive idea tries every possible permutation of the characters in one or both strings, computes the XOR result for each arrangement, and keeps the maximum value. For a string of length n, there are n! permutations, so the total work grows extremely fast. Time complexity is O(n! * n) because each permutation requires an XOR comparison across all positions, and space complexity is O(n!) if permutations are stored. This approach mainly helps build intuition about how rearrangement affects XOR but is impractical even for moderate input sizes.

Approach 2: Greedy Bit Counting (O(n) time, O(1) space)

The XOR operation returns 1 when bits differ (0 ^ 1 or 1 ^ 0). Because you can rearrange characters freely, the exact positions do not matter—only the counts of 0s and 1s matter. Count how many 1s and 0s appear in each string. Then greedily pair opposite bits to maximize mismatches: match 1s from one string with 0s from the other, and vice versa. The number of XOR 1s becomes min(count1A, count0B) + min(count0A, count1B). Iterate once through the strings to collect counts, then compute this formula. Time complexity is O(n) and space complexity is O(1).

This greedy reasoning works because rearrangement removes positional constraints. Instead of worrying about exact placements, you only maximize the number of differing pairs. Problems involving maximizing XOR often reduce to bit-level counting or greedy pairing, especially when reordering is allowed.

Understanding this pattern is useful in problems involving greedy algorithms, bit manipulation, and binary string processing. Many interview questions follow the same principle: transform positional constraints into frequency counts when rearrangement is permitted.

Recommended for interviews: The greedy counting approach is what interviewers expect. Mentioning the brute force permutation idea shows you understand the search space, but deriving the frequency-based formula demonstrates algorithmic insight and leads to the optimal O(n) solution.