1722. Minimize Hamming Distance After Swap Operations

2 challenges:

Given index a, index b are swappable, index b and index c are swappable, then we can swap index a and index c without side effect. It means you may use b to help move value at index a to index c, and meanwhile move value at index c to index a, however value at index b can stay at index b after all the movements. This analysis drives us to consider building connection group for indexes that are inter-swappable, and UF is a good data structure for this.

Proof: Given index 0 and 1 are swappable, and index 1 and 2 are swappable

a, b, c
b, a, c (by swapping index 0 and 1)
b, c, a (by swapping index 1 and 2)
c, b, a (by swapping index 0 and 1)

Given index 0 and 1 are swappable, index 1 and 2 are swappable, index 2 and 3 are swappable, prove that index 0 and 3 are swappable

a, b, c, d
b, a, c, d (by swapping index 0, 1)
b, d, c, a (based on first example)
d, b, c, a (by swapping index 0, 1)

No matter how long the swappable chain is, we can convert the problem to the base case where there are only 3 elements.

Once connection groups are built, I was stuck at how to calculate the hamming distance. building counters = collections.defaultdict(collections.Counter) so that counters[root] is the frequencies of each number under root.

counters[root][s] += 1
counters[root][t] -= 1

is equal to

        for i, s in enumerate(source):
            root = find(i)
            counters[root][s] += 1
        
        res = 0
        for i, t in enumerate(target):
            root = find(i)
            if counters[root][t] > 0:
                counters[root][t] -= 1
            else:
                res += 1
                
        return res

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        
        def find(i):
            while parent[i] != i:
                parent[i] = parent[parent[i]]
                i = parent[i]
            return i
        
        def union(i, j):
            root_i, root_j = find(i), find(j)
            if root_i != root_j:
                if wight[root_i] > wight[root_j]:
                    parent[root_j] = root_i
                    wight[root_i] += wight[root_j]
                else:
                    parent[root_i] = root_j
                    wight[root_j] += wight[root_i]
        
        n = len(source)
        parent = [i for i in range(n)]
        wight = [1 for i in range(n)]
        for i, j in allowedSwaps:
            union(i, j)
        
        counters = collections.defaultdict(collections.Counter)
        for i, (s, t) in enumerate(zip(source, target)):
            root = find(i)
            counters[root][s] += 1
            counters[root][t] -= 1
        
        res = 0
        for root, counter in counters.items():
            for num in counter:
                if counter[num] > 0:
                    res += counter[num]
        return res

1722. Minimize Hamming Distance After Swap Operations - cocoder39/coco39_LC GitHub Wiki