Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Indices connected by allowed swaps can exchange values through a sequence of swaps, permitting arbitrary rearrangement inside each connected component. Values cannot move between components, so the best matching depends only on each component's multiset of source values.

Approach

Union the endpoints of every allowed swap. Group source-value frequencies by the resulting component representative. Then visit each target position: consume one matching value from its component if available, otherwise count a mismatch. Each available matching copy can satisfy exactly one target occurrence, so consuming it greedily maximizes matches within that independent component. Return the total unmatched positions. Duplicate values require frequencies rather than simple membership sets.

class UF:
    def __init__(self, n):
        self.par = [i for i in range(n)]
    
    def find(self, x):
        if not self.par[x] == x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
        if pa != pb: self.par[pb] = pa

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        uf = UF(n)

        for a, b in allowedSwaps:
            uf.union(a, b)
        
        groups = defaultdict(lambda: defaultdict(int))
        for i in range(n):
            groups[uf.find(i)][source[i]] += 1

        print(groups)
        res = 0
        for i in range(n):
            g = groups[uf.find(i)]
            t = target[i]
            if g[t] > 0: g[t] -= 1
            else: res += 1

        return res

Complexity analysis

Let n = source.length and e = allowedSwaps.length. Path compression without union by rank gives O((n + e) log n) amortized time, with expected constant-time frequency-map operations, and O(n) auxiliary space. Python additionally formats and prints its component maps: O(n) output characters under the bounded index/value constraints, with extra formatting and I/O overhead. Its recursive find can reach O(n) depth on an adversarial legal parent chain and exceed the default recursion limit unless the runner raises it sufficiently. JavaScript uses iterative find.