1
// Main function
2
var numSimilarGroups = function (strs) {
3
  const n = strs.length,
4
    uf = new UnionFind(n);
5

6
  // Compare each string with all other string
7
  for (let i = 0; i < n; ++i) {
8
    for (let j = i + 1; j < n; ++j) {
9
      if (isSimilar(strs[i], strs[j])) uf.union(i, j);
10
    }
11
  }
12
  return uf.count;
13
  // uf.count gives number of non connected components in UnionFind data structure
14
};
15

16
// UnionFind Data Structure with Strongly connected components
17
class UnionFind {
18
  constructor(n) {
19
    this.parent = Array(n)
20
      .fill()
21
      .map((_, i) => i);
22
    this.count = n; // Keep track of number of groups
23
  }
24
  find(i) {
25
    if (this.parent[i] !== i) this.parent[i] = this.find(this.parent[i]);
26
    return this.parent[i];
27
  }
28
  union(i, j) {
29
    const x = this.find(i),
30
      y = this.find(j);
31
    if (x !== y) (this.parent[y] = x), this.count--;
32
  }
33
}
34

35
// Function to check if 2 strings are different at less than 2 positions or not
36
var isSimilar = function (str1, str2) {
37
  if (str1 === str2) return true;
38
  let count = 0;
39
  for (let i = 0; i < str1.length; ++i) {
40
    if (str1[i] !== str2[i] && ++count > 2) return false;
41
  }
42
  return true;
43
};