Minimize Hamming Distance After Swap Operations
Problem
Given source, target arrays and allowedSwaps[i]=[a,b] meaning indices a and b may be swapped any number of times, return the minimum possible hamming distance after operations.
source=[1,2,3,4], target=[2,1,4,5], allowedSwaps=[[0,1],[2,3]]1def minimum_hamming_distance(source, target, allowedSwaps):
n = len(source)
p = list(range(n))
def find(x):
while p[x] != x:
p[x] = p[p[x]]; x = p[x]
return x
for a, b in allowedSwaps:
p[find(a)] = find(b)
from collections import defaultdict, Counter
groups = defaultdict(list)
for i in range(n):
groups[find(i)].append(i)
diff = 0
for idxs in groups.values():
cs = Counter(source[i] for i in idxs)
ct = Counter(target[i] for i in idxs)
common = sum((cs & ct).values())
diff += len(idxs) - common
return difffunction minimumHammingDistance(source, target, allowedSwaps) {
const n = source.length;
const p = [...Array(n).keys()];
const find = x => { while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; } return x; };
for (const [a, b] of allowedSwaps) p[find(a)] = find(b);
const groups = new Map();
for (let i = 0; i < n; i++) {
const r = find(i);
if (!groups.has(r)) groups.set(r, []);
groups.get(r).push(i);
}
let diff = 0;
for (const idxs of groups.values()) {
const cs = new Map(), ct = new Map();
for (const i of idxs) { cs.set(source[i], (cs.get(source[i]) || 0) + 1); ct.set(target[i], (ct.get(target[i]) || 0) + 1); }
let common = 0;
for (const [k, v] of cs) common += Math.min(v, ct.get(k) || 0);
diff += idxs.length - common;
}
return diff;
}class Solution {
int[] p;
int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
p = new int[n]; for (int i = 0; i < n; i++) p[i] = i;
for (int[] e : allowedSwaps) p[find(e[0])] = find(e[1]);
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(find(i), k -> new ArrayList<>()).add(i);
int diff = 0;
for (List<Integer> idxs : groups.values()) {
Map<Integer, Integer> cs = new HashMap<>(), ct = new HashMap<>();
for (int i : idxs) { cs.merge(source[i], 1, Integer::sum); ct.merge(target[i], 1, Integer::sum); }
int common = 0;
for (var e : cs.entrySet()) common += Math.min(e.getValue(), ct.getOrDefault(e.getKey(), 0));
diff += idxs.size() - common;
}
return diff;
}
}class DSU { public: vector<int> p; DSU(int n): p(n) { iota(p.begin(), p.end(), 0); } int find(int x){ while(p[x]!=x){p[x]=p[p[x]];x=p[x];} return x; }};
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
int n = source.size();
DSU d(n);
for (auto& e : allowedSwaps) d.p[d.find(e[0])] = d.find(e[1]);
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; i++) groups[d.find(i)].push_back(i);
int diff = 0;
for (auto& [_, idxs] : groups) {
unordered_map<int,int> cs, ct;
for (int i : idxs) { cs[source[i]]++; ct[target[i]]++; }
int common = 0;
for (auto& [k, v] : cs) common += min(v, ct.count(k) ? ct[k] : 0);
diff += (int)idxs.size() - common;
}
return diff;
}Explanation
The key realization is that if indices can be swapped, even indirectly through a chain of allowed swaps, then within that connected group you can rearrange the values freely. So the order inside a group does not matter, only which values are present.
We use Union-Find to merge every pair in allowedSwaps, so indices that can reach each other end up in the same group (same root via find).
For each group we compare the multiset of source values to the multiset of target values at those indices. The number of values they share (common) is how many positions we can make match. Everything left over must mismatch, so we add len(idxs) - common to the answer.
We count shared values with a Counter intersection, which takes the minimum count of each value across source and target.
Example: source=[1,2,3,4], target=[2,1,4,5], swaps [[0,1],[2,3]]. Group {0,1} has values {1,2} matching target {2,1} fully. Group {2,3} has {3,4} vs {4,5}: only 4 matches, so one mismatch remains. Answer is 1.