#1722

Minimize Hamming Distance After Swap Operations

specialist · 880 · lc medium +31 · verified · 49.2% accepted · 896 likes · top 36%

Description

You are given two integer arrays source and target of length n, and allowedSwaps[i] = [ai, bi] permitting swaps of source[ai] and source[bi] any number of times. The Hamming distance counts positions where they differ.

Return the minimum Hamming distance achievable after any sequence of allowed swaps.

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

Code

1

2

3

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int: