Minimize Hamming Distance After Swap Operations LeetCode solution in Python

1
# Runtime: 1385 ms (Top 99.43%) | Memory: 59.9 MB (Top 71.02%)
2
class UnionFind:
3
    def __init__(self, n):
4
        self.roots = [i for i in range(n)]
5

6
    def find(self, v):
7
        if self.roots[v] != v:
8
            self.roots[v] = self.find(self.roots[v])
9

10
        return self.roots[v]
11

12
    def union(self, u, v):
13
        self.roots[self.find(u)] = self.find(v)
14

15

16
class Solution:
17
    def minimumHammingDistance(
18
        self, source: List[int], target: List[int], allowedSwaps: List[List[int]]
19
    ) -> int:
20
        uf = UnionFind(len(source))
21
        for idx1, idx2 in allowedSwaps:
22
            uf.union(idx1, idx2)
23

24
        m = collections.defaultdict(set)
25
        for i in range(len(source)):
26
            m[uf.find(i)].add(i)
27

28
        res = 0
29
        for indices in m.values():
30
            freq = {}
31
            for i in indices:
32
                freq[source[i]] = freq.get(source[i], 0) + 1
33
                freq[target[i]] = freq.get(target[i], 0) - 1
34
            res += sum(val for val in freq.values() if val > 0)
35

36
        return res