Minimize Hamming Distance After Swap Operations

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:


Solution:

1. use union find to find all groups of indexes that can be swapped
2. for each group (grouped by root of the UF tree), generate a frequency map of source numbers
   for examples, if we have 
source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Then we have two UF groups, [0,1] [2,3] as well
assume 0 and 2 are the roots, we will have
<0, { <0, 1>, <1, 1>  }> and <2, {{2, 1}, <3, 1>  }>
3. then for each target number, find its group first, if we can't find it, or if the group doesn't contain the target number, increase the result count, otherwise we assign a source number to the target number, and decrement the source number's frequency in the map


class Solution {
    class UF {
        int[] parent;
        int[] size;
        
        public UF(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i ++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        public int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return;
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    }
    
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        UF uf = new UF(n);
        for (int[] edge : allowedSwaps) {
            uf.union(edge[0], edge[1]);
        }
        Map<Integer, Map<Integer, Integer>> groups = new HashMap();
        for (int i = 0; i < n; i ++) {
            int root = uf.find(i);
            Map<Integer, Integer> sourceNums = groups.computeIfAbsent(root, k -> new HashMap());
            sourceNums.put(source[i], sourceNums.getOrDefault(source[i], 0) + 1);
        }
        int res = 0;
        for (int i = 0; i < n; i ++) {
            int t = target[i];
            int root = uf.find(i);
            Map<Integer, Integer> sourceNums = groups.get(root);
            if (sourceNums == null || sourceNums.getOrDefault(t, 0) == 0) {
                res ++;
            } else {
                sourceNums.put(t, sourceNums.get(t) - 1);
            }
        }
        return res;
    }
}