1722. Minimize Hamming Distance After Swap Operations

/**
 * Problem: LeetCode 1722 - Minimize Hamming Distance After Swap Operations
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.HashMap;
import java.util.Map;

class Solution {
    static class DSU {
        int[] parent;
        int[] rank;
        
        public DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        
        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }
        
        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
            }
        }
    }

    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        final int n = source.length;
        DSU dsu = new DSU(n);
        
        for (int[] swapOp : allowedSwaps) {
            dsu.union(swapOp[0], swapOp[1]);
        }
        
        // Group frequencies of source elements by their connected component root
        Map<Integer, Map<Integer, Integer>> componentCounts = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int root = dsu.find(i);
            componentCounts.computeIfAbsent(root, k -> new HashMap<>())
                           .merge(source[i], 1, Integer::sum);
        }
        
        // Count positions where target[i] cannot be matched from the component
        int hammingDistance = 0;
        for (int i = 0; i < n; ++i) {
            int root = dsu.find(i);
            Map<Integer, Integer> counts = componentCounts.get(root);
            int val = target[i];
            int available = counts.getOrDefault(val, 0);
            
            if (available > 0) {
                counts.put(val, available - 1);
            } else {
                hammingDistance++;
            }
        }
        
        return hammingDistance;
    }
}

"""
Problem: LeetCode 1722 - Minimize Hamming Distance After Swap Operations
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List
from collections import defaultdict


class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, i: int) -> int:
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i: int, j: int) -> None:
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_j] = root_i
                self.rank[root_i] += 1


class Solution:
    def minimumHammingDistance(
        self, source: List[int], target: List[int], allowedSwaps: List[List[int]]
    ) -> int:
        n = len(source)
        dsu = DSU(n)

        for u, v in allowedSwaps:
            dsu.union(u, v)

        # Count frequencies of source elements grouped by component root
        component_counts = defaultdict(lambda: defaultdict(int))
        for i in range(n):
            root = dsu.find(i)
            component_counts[root][source[i]] += 1

        hamming_distance = 0
        for i in range(n):
            root = dsu.find(i)
            counts = component_counts[root]
            val = target[i]
            if counts[val] > 0:
                counts[val] -= 1
            else:
                hamming_distance += 1

        return hamming_distance

/**
 * Problem: LeetCode 1722 - Minimize Hamming Distance After Swap Operations
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <numeric>
#include <unordered_map>

using namespace std;

class Solution {
    struct DSU {
        vector<int> parent;
        vector<int> rank;

        DSU(int n) : parent(n), rank(n, 0) {
            iota(parent.begin(), parent.end(), 0);
        }

        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        void unite(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
            }
        }
    };

public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        DSU dsu(n);

        for (const auto& swapOp : allowedSwaps) {
            dsu.unite(swapOp[0], swapOp[1]);
        }

        // Count frequencies of elements in source for each connected component
        unordered_map<int, unordered_map<int, int>> componentCounts;
        for (int i = 0; i < n; ++i) {
            int root = dsu.find(i);
            componentCounts[root][source[i]]++;
        }

        int hammingDistance = 0;
        for (int i = 0; i < n; ++i) {
            int root = dsu.find(i);
            auto& counts = componentCounts[root];
            int val = target[i];
            auto it = counts.find(val);
            if (it != counts.end() && it->second > 0) {
                it->second--;
            } else {
                hammingDistance++;
            }
        }

        return hammingDistance;
    }
};

/**
 * Problem: LeetCode 1722 - Minimize Hamming Distance After Swap Operations
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
class DSU {
    constructor(n) {
        this.parent = new Int32Array(n);
        this.rank = new Int32Array(n);
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }

    find(i) {
        if (this.parent[i] === i) return i;
        this.parent[i] = this.find(this.parent[i]);
        return this.parent[i];
    }

    union(i, j) {
        let rootI = this.find(i);
        let rootJ = this.find(j);
        if (rootI !== rootJ) {
            if (this.rank[rootI] < this.rank[rootJ]) {
                this.parent[rootI] = rootJ;
            } else if (this.rank[rootI] > this.rank[rootJ]) {
                this.parent[rootJ] = rootI;
            } else {
                this.parent[rootJ] = rootI;
                this.rank[rootI]++;
            }
        }
    }
}

/**
 * @param {number[]} source
 * @param {number[]} target
 * @param {number[][]} allowedSwaps
 * @return {number}
 */
var minimumHammingDistance = function(source, target, allowedSwaps) {
    const n = source.length;
    const dsu = new DSU(n);

    for (let i = 0; i < allowedSwaps.length; i++) {
        dsu.union(allowedSwaps[i][0], allowedSwaps[i][1]);
    }

    // Map: root -> Map<value, count>
    const componentCounts = new Map();
    for (let i = 0; i < n; i++) {
        const root = dsu.find(i);
        let map = componentCounts.get(root);
        if (!map) {
            map = new Map();
            componentCounts.set(root, map);
        }
        map.set(source[i], (map.get(source[i]) || 0) + 1);
    }

    let hammingDistance = 0;
    for (let i = 0; i < n; i++) {
        const root = dsu.find(i);
        const map = componentCounts.get(root);
        const val = target[i];
        const count = map.get(val) || 0;
        if (count > 0) {
            map.set(val, count - 1);
        } else {
            hammingDistance++;
        }
    }

    return hammingDistance;
};