1
class Solution {
2
  int[] parent;
3
  int[] rank;
4

5
  public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
6
    parent = new int[s.length()];
7
    rank = new int[s.length()];
8
    for (int i = 0; i < parent.length; i++) {
9
      parent[i] = i;
10
      rank[i] = 0;
11
    }
12

13
    // Union of All Pairs who belongs to same set
14
    for (List<Integer> l : pairs) {
15
      int i = l.get(0);
16
      int j = l.get(1);
17

18
      int il = find(i);
19
      int jl = find(j);
20
      if (il != jl) {
21
        union(il, jl);
22
      }
23
    }
24

25
    // To get the Character in sorted order
26
    PriorityQueue<Character>[] pq = new PriorityQueue[s.length()];
27
    for (int i = 0; i < pq.length; i++) {
28
      pq[i] = new PriorityQueue<>();
29
    }
30

31
    for (int i = 0; i < s.length(); i++) {
32
      int il = find(i);
33
      char ch = s.charAt(i);
34
      pq[il].add(ch);
35
    }
36

37
    StringBuilder sb = new StringBuilder();
38
    for (int i = 0; i < s.length(); i++) {
39
      int il = find(i);
40
      char ch = pq[il].remove();
41
      sb.append(ch);
42
    }
43

44
    return sb.toString();
45
  }
46

47
  int find(int x) {
48
    if (parent[x] == x) {
49
      return x;
50
    } else {
51
      parent[x] = find(parent[x]);
52
      return parent[x];
53
    }
54
  }
55

56
  void union(int x, int y) {
57
    if (rank[x] < rank[y]) {
58
      parent[x] = y;
59
    } else if (rank[y] < rank[x]) {
60
      parent[y] = x;
61
    } else {
62
      parent[x] = y;
63
      rank[y]++;
64
    }
65
  }
66
}