Groups of Strings LeetCode solution in Java

1
class Solution {
2
  public int[] groupStrings(String[] words) {
3
    int n = words.length;
4
    Arrays.sort(words, Comparator.comparingInt(String::length));
5
    int[] parents = new int[n];
6
    int[] ranks = new int[n];
7
    for (int i = 0; i < n; i++) parents[i] = i;
8
    Arrays.fill(ranks, 1);
9

10
    int[] masks = new int[n];
11
    for (int i = 0; i < n; i++) {
12
      int val = 0;
13
      for (int j = 0; j < words[i].length(); j++) {
14
        val += (1 << (words[i].charAt(j) - 'a'));
15
      }
16
      masks[i] = val;
17
    }
18
    Set<Integer> seen = new HashSet<>();
19
    for (int i = 0; i < n; i++) {
20
      if (seen.contains(masks[i])) continue;
21
      for (int j = i + 1; j < n; j++) {
22
        if (words[i].length() + 1 < words[j].length()) break;
23
        int p1 = find(parents, i), p2 = find(parents, j);
24
        if (p1 == p2) continue;
25
        int a = masks[i], b = masks[j];
26
        if (a == b) merge(parents, ranks, p1, p2);
27
        int xor = a ^ b;
28
        int and = a & b;
29
        int xor1 = a ^ and, xor2 = b ^ and;
30
        if ((xor & (xor - 1)) == 0 || ((xor1 & (xor1 - 1)) == 0 && (xor2 & (xor2 - 1)) == 0)) {
31
          merge(parents, ranks, p1, p2);
32
        }
33
      }
34
      seen.add(masks[i]);
35
    }
36

37
    Map<Integer, Integer> map = new HashMap<>();
38
    int max = 1;
39
    for (int i = 0; i < n; i++) {
40
      int f = find(parents, i);
41
      int cnt = map.getOrDefault(f, 0) + 1;
42
      map.put(f, cnt);
43
      max = Math.max(max, cnt);
44
    }
45

46
    return new int[] {map.size(), max};
47
  }
48

49
  private int find(int[] parents, int i) {
50
    return parents[i] = parents[i] == i ? i : find(parents, parents[i]);
51
  }
52

53
  private void merge(int[] parents, int[] ranks, int i, int j) {
54
    int p1 = find(parents, i), p2 = find(parents, j);
55
    if (p1 == p2) return;
56
    if (ranks[p1] > ranks[p2]) {
57
      parents[p1] = p2;
58
      parents[i] = p2;
59
      ranks[p2]++;
60
      return;
61
    }
62
    parents[p2] = p1;
63
    parents[j] = p1;
64
    ranks[p1]++;
65
  }
66
}