14:T47b,class UnionFind { public: vector fa, rank; UnionFind(int n) { fa.resize(n); rank.resize(n, 0); for (int i = 0; i < n; ++i) fa[i] = i; } int find(int x) { if (fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } void unite(int x, int y) { int rootX = find(x), rootY = find(y); if (rootX != rootY) { if (rank[rootX] < rank[rootY]) swap(rootX, rootY); fa[rootY] = rootX; if (rank[rootX] == rank[rootY]) rank[rootX]++; } } }; class Solution { public: int minimumHammingDistance(vector& source, vector& target, vector>& allowedSwaps) { int n = source.size(); UnionFind uf(n); for (auto& swap : allowedSwaps) uf.unite(swap[0], swap[1]); unordered_map> map; for (int i = 0; i < n; ++i) map[uf.find(i)][source[i]]++; int res = 0; for (int i = 0; i < n; ++i) { int root = uf.find(i); if (map[root][target[i]] > 0) map[root][target[i]]--; else res++; } return res; } };15:T4e9,class UnionFind { constructor(n) { this.fa = Array.from({length: n}, (_, i) => i); this.rank = new Array(n).fill(0); } find(x) { if (this.fa[x] !== x) this.fa[x] = this.find(this.fa[x]); return this.fa[x]; } union(x, y) { let rootX = this.find(x), rootY = this.find(y); if (rootX !== rootY) { if (this.rank[rootX] < this.rank[rootY]) { let temp = rootX; rootX = rootY; rootY = temp; } this.fa[rootY] = rootX; if (this.rank[rootX] === this.rank[rootY]) this.rank[rootX]++; } } } var minimumHammingDistance = function(source, target, allowedSwaps) { let n = source.length; let uf = new UnionFind(n); for (let swap of allowedSwaps) uf.union(swap[0], swap[1]); let map = new Map(); for (let i = 0; i < n; i++) { let root = uf.find(i); if (!map.has(root)) map.set(root, new Map()); let g = map.get(root); g.set(source[i], (g.get(source[i]) || 0) + 1); } let res = 0; for (let i = 0; i < n; i++) { let root = uf.find(i); let g = map.get(root); if (g && g.get(target[i]) > 0) g.set(target[i], g.get(target[i]) - 1); else res++; } return res; };

Time Complexity

Space Complexity