362. Minimize Hamming Distance After Swap Operations

Every allowed swap is reversible, so the set of permutations reachable on source is exactly the orbit under the swap relation. Enumerate every reachable permutation and pick the one closest to target. This is exponential but illustrates what's being asked.

Approach

1. BFS or recursive expansion over permutations of source, swapping along edges in allowedSwaps.
2. For each reachable permutation, count Hamming distance to target.
3. Return the minimum.

Complexity

• Time: O(n! · n) worst case — only practical for tiny n.
• Space: O(n!) to memoise visited states.

import java.util.*;

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        Set<String> seen = new HashSet<>();
        String init = Arrays.toString(source);
        seen.add(init);
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(source.clone());
        int best = 0;
        for (int i = 0; i < n; i++) {
            if (source[i] != target[i]) best++;
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int ham = 0;
            for (int i = 0; i < n; i++) {
                if (cur[i] != target[i]) ham++;
            }
            best = Math.min(best, ham);
            for (int[] swap : allowedSwaps) {
                int[] nxt = cur.clone();
                int tmp = nxt[swap[0]];
                nxt[swap[0]] = nxt[swap[1]];
                nxt[swap[1]] = tmp;
                String key = Arrays.toString(nxt);
                if (!seen.contains(key)) {
                    seen.add(key);
                    queue.offer(nxt);
                }
            }
        }
        return best;
    }
}

Allowed swaps define an equivalence on indices: if i can swap with j, and j with k, then i can reach k via two swaps. So indices in the same connected component can be freely permuted among themselves. Within one component, the source values at those indices form an unordered multiset — we just count how many of those values match target at the corresponding positions, and the rest are mismatches.

Why a swap component lets us permute freely

Consider three indices i, j, k with allowed swaps (i, j) and (j, k). Then via swaps we can produce any permutation of the values at those three indices:

• Identity (do nothing).
• Swap i ↔ j.
• Swap j ↔ k.
• Swap i ↔ j, then j ↔ k: a cyclic shift i → j → k → i.
• Swap j ↔ k, then i ↔ j: the other cyclic shift.
• Swap i ↔ j, then j ↔ k, then i ↔ j: ends up as i ↔ k.

So any subset of indices in one swap-component can be permuted into any order. That collapses the problem: within one component, the multiset of source values at those indices is the only thing that matters.

Steps

1. Union-Find on indices. Initialise parent[i] = i. For every (a, b) in allowedSwaps, union the roots of a and b.
2. Group indices by root. groups[root].append(i) for each i.
3. Match within each group. For each group:
   • Build a Counter of source[i] for i in the group.
   • For each i in the group, look at target[i]: if the counter still has at least one of that value, decrement it (a free match, no cost). Otherwise this position will be a mismatch — add 1 to the running total.
4. Return the total.

Walk-through

source = [1, 2, 3, 4], target = [2, 1, 4, 5], allowedSwaps = [[0, 1], [2, 3]].

Union step. union(0, 1), union(2, 3). Components: {0, 1} and {2, 3}.

Component {0, 1}:

Component contributes 0 mismatches — both positions matchable.

Component {2, 3}:

Component contributes 1 mismatch.

Total: 0 + 1 = 1. ✓

Why the counter approach gives the minimum

Inside one component, we can place any value-from-source into any index-of-the-component. So the question reduces to: "how many positions in target[component] can I cover with values from Counter(source[component])?". That's exactly what the greedy counter check computes — match each target slot if a value is still available, else count it as a mismatch.

Edge cases

• No swaps: every index is its own component. The answer is just the original Hamming distance between source and target.
• All indices in one component: we can match any source value to any target slot. The mismatches equal the size of the symmetric difference of the two multisets.

Complexity

• Time: O((n + m) · α(n)) where m = len(allowedSwaps) and α is the inverse Ackermann function (effectively constant).
• Space: O(n) — Union-Find arrays plus the per-component counters.