1202. Smallest String With Swaps

T: O(nlogn)

S: O(n)

```java
class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);
        
        for (List<Integer> pair : pairs) {
            uf.union(pair.get(0), pair.get(1));
        }

        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            int groupParent = uf.find(i);
            map.putIfAbsent(groupParent, new PriorityQueue<>());
            map.get(groupParent).offer(c[i]); // put char belong to this parent (same group, same parent)
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < c.length; i++) {
            int groupParent = uf.find(i);
            sb.append(map.get(groupParent).poll()); // then get sorted char from each char's group
        }
        return sb.toString();
    }
    class UnionFind {
        int[] parent;
        int count;
        UnionFind(int n) {
            this.parent = new int[n];
            this.count = n;
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
            }
        }
        public boolean union(int i, int j) {
            int x = find(i);
            int y = find(j);
            if (x != y) { // use smaller one as the parent node
                if (x < y) {
                    parent[y] = x;
                } else {
                    parent[x] = y;
                }
                this.count--;
                return true;
            }
            return false;
        }
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        private int getComponentCount() {
            return this.count;
        }

    }
}

/*

dcab
0123

0. 3
 12

0. 3
  12 
0. 2   


cba
01
 12
*/
```