## DEV Community

Abhishek Chaudhary

Posted on

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

SOLUTION:

``````from collections import defaultdict, Counter

class Solution:
def dfs(self, graph, node, visited):
for j in graph[node]:
if j not in visited:
self.dfs(graph, j, visited)

def hammingDist(self, actr, bctr, n):
ctr = 0
for x in actr:
ctr += min(actr[x], bctr[x])
return n - ctr

def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
graph = defaultdict(list)
n = len(source)
dist = 0
for a, b in allowedSwaps:
graph[a].append(b)
graph[b].append(a)
globalvisited = set()
for x in graph:
if x not in globalvisited:
currvisited = {x}
self.dfs(graph, x, currvisited)
nv = len(currvisited)
sourcenums = Counter([source[p] for p in currvisited])
targetnums = Counter([target[p] for p in currvisited])
dist += self.hammingDist(sourcenums, targetnums, nv)
globalvisited.update(currvisited)
for i in range(n):
if i not in globalvisited and source[i] != target[i]:
dist += 1
return dist
``````
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}