1
var smallestStringWithSwaps = function (s, pairs) {
2
  const uf = new UnionFind(s.length);
3
  pairs.forEach(([x, y]) => uf.union(x, y));
4

5
  const result = [];
6
  for (const [root, charIndex] of Object.entries(uf.disjointSets())) {
7
    let chars = charIndex.map((i) => s[i]);
8
    chars.sort();
9
    charIndex.forEach((charIndex, i) => (result[charIndex] = chars[i]));
10
  }
11

12
  return result.join("");
13
};
14

15
class UnionFind {
16
  constructor(len) {
17
    this.roots = Array.from({ length: len }).map((_, i) => i);
18
    this.rank = Array.from({ length: len }).fill(1);
19
  }
20

21
  find(x) {
22
    if (x == this.roots[x]) {
23
      return x;
24
    }
25
    return (this.roots[x] = this.find(this.roots[x]));
26
  }
27

28
  union(x, y) {
29
    let rootX = this.find(x);
30
    let rootY = this.find(y);
31

32
    if (this.rank[rootX] > this.rank[rootY]) {
33
      this.roots[rootY] = rootX;
34
    } else if (this.rank[rootX] < this.rank[rootY]) {
35
      this.roots[rootX] = rootY;
36
    } else {
37
      // ranks equal
38
      this.roots[rootY] = rootX;
39
      this.rank[rootX]++;
40
    }
41
  }
42

43
  disjointSets() {
44
    const ds = {};
45
    for (let i = 0; i < this.roots.length; i++) {
46
      let currentRoot = this.find(i);
47
      if (currentRoot in ds) {
48
        ds[currentRoot].push(i);
49
      } else {
50
        ds[currentRoot] = [i];
51
      }
52
    }
53
    return ds;
54
  }
55
}