交换字符串中的元素

/*
 * The idea is the same as the previous Java solution, using Union-Find to group connected indices.
 * This version leverages Java Streams to perform some of the operations in a more functional style.
 */
import java.util.*;
import java.util.stream.Collectors;

public class SmallestStringWithSwapsStream {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);

        // Union step for all pairs
        pairs.forEach(pair -> uf.union(pair.get(0), pair.get(1)));

        // Group all characters by root parent
        Map<Integer, List<Character>> charGroups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            charGroups.computeIfAbsent(root, k -> new ArrayList<>()).add(s.charAt(i));
        }

        // Sort the characters in each group
        charGroups.values().forEach(Collections::sort);

        // Reconstruct the smallest string by replacing characters in sorted order
        StringBuilder result = new StringBuilder(s);
        Map<Integer, Iterator<Character>> groupIterators = charGroups.entrySet().stream()
            .collect(Collectors.toMap(Map.Entry::getKey, e -> e.getValue().iterator()));
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            result.setCharAt(i, groupIterators.get(root).next());
        }

        return result.toString();
    }

    // Union-Find class
    class UnionFind {
        int[] parent;
        int[] rank;

        public UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

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

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX] += 1;
                }
            }
        }
    }
}