Maximum Number of Non-Overlapping Substrings LeetCode solution in Java

1
class Solution {
2
  public List<String> maxNumOfSubstrings(String s) {
3
    int n = s.length();
4
    int[] R = new int[26];
5
    int[] L = new int[26];
6
    Arrays.fill(R, -1);
7
    Arrays.fill(L, -1);
8
    BitSet[] bit = new BitSet[26];
9
    Arrays.setAll(bit, o -> new BitSet());
10
    for (int i = 0; i < n; i++) {
11
      R[s.charAt(i) - 'a'] = i; // last character index position
12
    }
13
    for (int i = n - 1; i >= 0; i--) {
14
      L[s.charAt(i) - 'a'] = i; // first character index position
15
    }
16
    for (int i = 0; i < 26; i++) { // add all characters between a character range.
17
      for (int j = L[i] + 1; j < R[i] && L[i] >= 0; j++) {
18
        bit[i].set(s.charAt(j) - 'a');
19
      }
20
    }
21
    boolean go = true;
22
    while (go) { // keep merging until there is no more range change.
23
      go = false;
24
      for (int i = 0; i < 26; i++) {
25
        for (int j = bit[i].nextSetBit(0); j >= 0; j = bit[i].nextSetBit(j + 1)) {
26
          bit[i].or(bit[j]); // add all characters from character j to i.
27
          int l = Math.min(L[i], L[j]);
28
          int r = Math.max(R[i], R[j]);
29
          go |= l != L[i] || r != R[i];
30
          L[i] = l;
31
          R[i] = r;
32
        }
33
      }
34
    }
35
    List<String> ans = new ArrayList<>();
36
    boolean[] seen = new boolean[n];
37
    for (int i = 0; i < 26; i++) { // populate the answer
38
      boolean ok = L[i] >= 0 && !seen[L[i]];
39
      for (int j = 0; j < 26 && ok; j++) {
40
        if (i != j && L[j] >= 0) { // only take those that has no smaller valid ranges.
41
          ok &= !(L[i] < L[j] && R[i] > R[j]);
42
        }
43
      }
44
      if (ok) {
45
        ans.add(s.substring(L[i], R[i] + 1));
46
        seen[L[i]] = true;
47
      }
48
    }
49
    return ans;
50
  }
51
}