Smallest String With Swaps solution and explanation

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def smallestStringWithSwaps(s, pairs):
    if not s:
        return ""
    n = len(s)
    uf = UnionFind(n)
    for x, y in pairs:
        uf.union(x, y)

    import collections
    groups = collections.defaultdict(list)
    for i in range(n):
        root = uf.find(i)
        groups[root].append(i)

    res = list(s)
    for indices in groups.values():
        sorted_chars = sorted(res[i] for i in indices)
        for i, char in zip(sorted(indices), sorted_chars):
            res[i] = char
    return ''.join(res)

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

class UnionFind {
public:
    std::vector<int> parent;
    UnionFind(int size) : parent(size) {
        for (int i = 0; i < size; ++i) parent[i] = i;
    }

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

    void union_sets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
};

std::string smallestStringWithSwaps(std::string s, std::vector<std::vector<int>>& pairs) {
    int n = s.size();
    UnionFind uf(n);
    for (auto& p : pairs) {
        uf.union_sets(p[0], p[1]);
    }
    std::unordered_map<int, std::vector<int>> groups;
    for (int i = 0; i < n; ++i) {
        groups[uf.find(i)].emplace_back(i);
    }
    for (auto& [_, indices] : groups) {
        std::string t = "";
        for (int index : indices) {
            t += s[index];
        }
        std::sort(t.begin(), t.end());
        for (size_t i = 0; i < indices.size(); ++i) {
            s[indices[i]] = t[i];
        }
    }
    return s;
}

import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (List<Integer> pair : pairs) {
            graph[pair.get(0)].add(pair.get(1));
            graph[pair.get(1)].add(pair.get(0));
        }

        boolean[] visited = new boolean[n];
        char[] res = s.toCharArray();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> indices = new ArrayList<>();
                List<Character> chars = new ArrayList<>();
                dfs(i, graph, visited, indices, chars, res);
                Collections.sort(indices);
                Collections.sort(chars);
                for (int j = 0; j < indices.size(); j++) {
                    res[indices.get(j)] = chars.get(j);
                }
            }
        }
        return new String(res);
    }

    private void dfs(int node, List<Integer>[] graph, boolean[] visited, List<Integer> indices, List<Character> chars, char[] res) {
        visited[node] = true;
        indices.add(node);
        chars.add(res[node]);
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited, indices, chars, res);
            }
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string SmallestStringWithSwaps(string s, IList<IList<int>> pairs) {
        int n = s.Length;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        foreach (var pair in pairs) {
            graph[pair[0]].Add(pair[1]);
            graph[pair[1]].Add(pair[0]);
        }

        bool[] visited = new bool[n];
        char[] result = s.ToCharArray();

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                var indices = new List<int>();
                var chars = new List<char>();
                DFS(i, graph, visited, indices, chars, result);
                indices.Sort();
                chars.Sort();
                for (int j = 0; j < indices.Count; j++) {
                    result[indices[j]] = chars[j];
                }
            }
        }
        return new string(result);
    }

    private void DFS(int node, List<int>[] graph, bool[] visited, List<int> indices, List<char> chars, char[] result) {
        visited[node] = true;
        indices.Add(node);
        chars.Add(result[node]);
        foreach (int neighbor in graph[node]) {
            if (!visited[neighbor]) {
                DFS(neighbor, graph, visited, indices, chars, result);
            }
        }
    }
}

function smallestStringWithSwaps(s: string, pairs: number[][]): string {
    const n = s.length;
    const p = new Array(n).fill(0).map((_, i) => i);
    const find = (x: number): number => {
        if (p[x] !== x) {
            p[x] = find(p[x]);
        }
        return p[x];
    };
    const d: string[][] = new Array(n).fill(0).map(() => []);
    for (const [a, b] of pairs) {
        p[find(a)] = find(b);
    }
    for (let i = 0; i < n; ++i) {
        d[find(i)].push(s[i]);
    }
    for (const e of d) {
        e.sort((a, b) => b.charCodeAt(0) - a.charCodeAt(0));
    }
    const ans: string[] = [];
    for (let i = 0; i < n; ++i) {
        ans.push(d[find(i)].pop()!);
    }
    return ans.join('');
}

func smallestStringWithSwaps(s string, pairs [][]int) string {
	n := len(s)
	p := make([]int, n)
	d := make([][]byte, n)
	for i := range p {
		p[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if p[x] != x {
			p[x] = find(p[x])
		}
		return p[x]
	}
	for _, pair := range pairs {
		a, b := pair[0], pair[1]
		p[find(a)] = find(b)
	}
	cs := []byte(s)
	for i, c := range cs {
		j := find(i)
		d[j] = append(d[j], c)
	}
	for i := range d {
		sort.Slice(d[i], func(a, b int) bool { return d[i][a] > d[i][b] })
	}
	for i := range cs {
		j := find(i)
		cs[i] = d[j][len(d[j])-1]
		d[j] = d[j][:len(d[j])-1]
	}
	return string(cs)
}

impl Solution {
    #[allow(dead_code)]
    pub fn smallest_string_with_swaps(s: String, pairs: Vec<Vec<i32>>) -> String {
        let n = s.as_bytes().len();
        let s = s.as_bytes();
        let mut disjoint_set: Vec<usize> = vec![0; n];
        let mut str_vec: Vec<Vec<u8>> = vec![Vec::new(); n];
        let mut ret_str = String::new();

        // Initialize the disjoint set
        for i in 0..n {
            disjoint_set[i] = i;
        }

        // Union the pairs
        for pair in pairs {
            Self::union(pair[0] as usize, pair[1] as usize, &mut disjoint_set);
        }

        // Initialize the return vector
        for (i, c) in s.iter().enumerate() {
            let p_c = Self::find(i, &mut disjoint_set);
            str_vec[p_c].push(*c);
        }

        // Sort the return vector in reverse order
        for cur_vec in &mut str_vec {
            cur_vec.sort();
            cur_vec.reverse();
        }

        // Construct the return string
        for i in 0..n {
            let index = Self::find(i, &mut disjoint_set);
            ret_str.push(str_vec[index].last().unwrap().clone() as char);
            str_vec[index].pop();
        }

        ret_str
    }

    #[allow(dead_code)]
    fn find(x: usize, d_set: &mut Vec<usize>) -> usize {
        if d_set[x] != x {
            d_set[x] = Self::find(d_set[x], d_set);
        }
        d_set[x]
    }

    #[allow(dead_code)]
    fn union(x: usize, y: usize, d_set: &mut Vec<usize>) {
        let p_x = Self::find(x, d_set);
        let p_y = Self::find(y, d_set);
        d_set[p_x] = p_y;
    }
}