1202. Smallest String With Swaps

class Solution {
    private static class UnionFind {
        private final int[] parent;

        public UnionFind(int n) {
            this.parent = new int[n];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x), yRoot = getRoot(y);
            if (xRoot == yRoot) {
                return;
            }

            parent[xRoot] = yRoot;
        }

        private int getRoot(int x) {
            if (x != parent[x]) {
                parent[x] = getRoot(parent[x]);
            }

            return parent[x];
        }
    }

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        UnionFind unionFind = new UnionFind(s.length());
        for (List<Integer> pair : pairs) {
            unionFind.union(pair.get(0), pair.get(1));
        }

        Map<Integer, Queue<Character>> rootIndexToCharQueueMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            int rootIndex = unionFind.getRoot(i);
            rootIndexToCharQueueMap.computeIfAbsent(rootIndex, key -> new PriorityQueue<>()).offer(s.charAt(i));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            int rootIndex = unionFind.getRoot(i);
            sb.append(rootIndexToCharQueueMap.get(rootIndex).poll());
        }

        return sb.toString();
    }
}

注意题解未采用边构建并查集边构建集合的方式，而是将并查集构建完成后，扫描一遍字符串构建根节点与节点列表的映射，且此时选择的数据结构为优先队列，因为优先队列有序且支持重复元素，所以此处不能选用 TreeSet。

References

1202. Smallest String With Swaps