Krammer's blog

https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/ from Google

Thinking process:

From the third example, we know that allowedSwap can have overlap like this [[0,4],[4,2],[1,3],[1,4]]. So [0,4] and [4,2] has a common index 4, which means the elements at index 0,2,4 can swap arbitrary. This means that the allowedSwap can form some kind of group, and all the elements in the same group can change the order to whatever we want.

This reminds me to use union find. We can group those allowedSwaps together if there’s any overlap. After that, we just need a map to calculate the number of each elements showing up in the same group in source, and compare it against the same map in target.

Here is the code.

 1class Solution {
 2public:
 3    vector<int> p;
 4    int f(int x) {
 5        if (p[x] == x) return x;
 6        return p[x] = f(p[x]);
 7    }
 8    void u(int x, int y) {
 9        int a = f(x);
10        int b = f(y);
11        p[a] = b;
12    }
13    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
14        int N = source.size();
15        p.resize(N);
16        for (int i=0; i<N; i++) p[i] = i;
17        for (auto a : allowedSwaps) {
18            u(a[0], a[1]);
19        }
20        unordered_map<int, unordered_map<int, int>> mp;
21        for (int i=0; i<N; i++) {
22            int x = f(i);
23            mp[x][source[i]]++;
24        }
25        for (int i=0; i<N; i++) {
26            int x = f(i);
27            mp[x][target[i]]--;
28        }
29        int ans = 0;
30        for (auto [k, v] : mp) {
31            for (auto [k1, v1] : v) {
32                ans += abs(v1);
33            }
34        }
35        return ans/2;
36    }
37};

Editorial: LeetCode 1722 Minimize Hamming Distance After Swap Operations