1722. 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:

• `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`

1722. Minimize Hamming Distance After Swap Operations
``````struct Solution;

use std::collections::HashMap;
use std::collections::HashSet;

struct UnionFind {
parent: Vec<usize>,
n: usize,
}

impl UnionFind {
fn new(n: usize) -> Self {
let parent = (0..n).collect();
UnionFind { parent, n }
}
fn find(&mut self, i: usize) -> usize {
let j = self.parent[i];
if i == j {
j
} else {
self.parent[i] = self.find(j);
self.parent[i]
}
}

fn union(&mut self, mut i: usize, mut j: usize) {
i = self.find(i);
j = self.find(j);
if i != j {
let min = i.min(j);
self.parent[i] = min;
self.parent[j] = min;
}
}
}

impl Solution {
fn minimum_hamming_distance(
source: Vec<i32>,
target: Vec<i32>,
allowed_swaps: Vec<Vec<i32>>,
) -> i32 {
let n = source.len();
let mut uf = UnionFind::new(n);
for swap in allowed_swaps {
let i = swap[0] as usize;
let j = swap[1] as usize;
uf.union(i, j);
}
let mut source_group: HashMap<usize, HashMap<i32, usize>> = HashMap::new();
let mut target_group: HashMap<usize, HashMap<i32, usize>> = HashMap::new();
let mut groups: HashMap<usize, HashSet<i32>> = HashMap::new();
for i in 0..n {
let g = uf.find(i);
*source_group
.entry(g)
.or_default()
.entry(source[i])
.or_default() += 1;
*target_group
.entry(g)
.or_default()
.entry(target[i])
.or_default() += 1;
groups.entry(g).or_default().insert(source[i]);
groups.entry(g).or_default().insert(target[i]);
}
let mut paired = 0;
for (g, vals) in &groups {
for x in vals {
let s_cnt = source_group[g].get(x).unwrap_or(&0);
let t_cnt = target_group[g].get(x).unwrap_or(&0);
paired += s_cnt.min(t_cnt);
}
}
(n - paired) as i32
}
}

#[test]
fn test() {
let source = vec![1, 2, 3, 4];
let target = vec![2, 1, 4, 5];
let allowed_swaps = vec_vec_i32![[0, 1], [2, 3]];
let res = 1;
assert_eq!(
Solution::minimum_hamming_distance(source, target, allowed_swaps),
res
);
let source = vec![1, 2, 3, 4];
let target = vec![1, 3, 2, 4];
let allowed_swaps = vec_vec_i32![];
let res = 2;
assert_eq!(
Solution::minimum_hamming_distance(source, target, allowed_swaps),
res
);
let source = vec![5, 1, 2, 4, 3];
let target = vec![1, 5, 4, 2, 3];
let allowed_swaps = vec_vec_i32![[0, 4], [4, 2], [1, 3], [1, 4]];
let res = 0;
assert_eq!(
Solution::minimum_hamming_distance(source, target, allowed_swaps),
res
);
}
``````