Description

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]] Output: 1 Explanation: source can be transformed the following way:

• Swap indices 0 and 1: source = [2,1,3,4]
• Swap indices 2 and 3: source = [2,1,4,3] The Hamming distance of source and target is 1 as they differ in 1 position: index 3. Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = [] Output: 2 Explanation: There are no allowed swaps. The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2. Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]] Output: 0

Constraints:

n == source.length == target.length 1 <= n <= 105 1 <= source[i], target[i] <= 105 0 <= allowedSwaps.length <= 105 allowedSwaps[i].length == 2 0 <= ai, bi <= n - 1 ai != bi

Solution

Since we are allowed to swap as many times as we want, we can partition the arrays into disjoint sets based on the allowed swaps. Then within the disjoint set, we can arrange the source array as close to the target array as possible and calculate the hamming distance. The result would be the sum of all the hamming distance for the disjoint sets.

Below is the implementation

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        '''
        if there is not allowedSwaps. Then ret is ham(source, target)
        
        [1, 2, 3, 4] [2, 1, 4, 5]
        [[0,1],[2,3]]
        if we partition the source array into disjoint sets according to allowed swaps, then for each set we calculate the hamming distance between it and corresponding target. The ret is the sum of all the hamming distance
        '''
        return self.helper(source, target, allowedSwaps)
        
    def helper(self, source, target, allowedSwaps):
        n = len(source)
        uf = UF(n)
        for swap in allowedSwaps:
            x, y = swap
            uf.union(x, y)
        s = collections.defaultdict(lambda:collections.defaultdict(int))
        t = collections.defaultdict(lambda:collections.defaultdict(int))
        for i in range(n):
            s[uf.find(i)][source[i]] += 1
            t[uf.find(i)][target[i]] += 1
        ret = 0
        for key1 in s:
            for key2 in s[key1]:
                if s[key1][key2] > t[key1][key2]:
                    ret += s[key1][key2] - t[key1][key2]
        return ret
    
        
        
class UF:
    
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.size = [1 for i in range(n)]
    
    def find(self, x):
        while x != self.parent[x]:
            x = self.parent[x]
        return x

    def union(self, x, y):
        parent_x = self.find(x)
        parent_y = self.find(y)
        if parent_x != parent_y:
            if self.size[parent_x] > self.size[parent_y]:#add y to x
                self.parent[parent_y] = parent_x
                self.size[parent_x] += self.size[parent_y]
            else:
                self.parent[parent_x] = parent_y #add x to y
                self.size[parent_y] += self.size[parent_x]
        return