Distinct Echo Substrings LeetCode solution in Java

1
class Solution {
2
  private static final int PRIME = 101;
3
  private static final int MOD = 1_000_000_007;
4

5
  public int distinctEchoSubstrings(String text) {
6
    int n = text.length();
7

8
    // dp[i][j] : hash value of text[i:j]
9
    int[][] dp = new int[n][n];
10
    for (int i = 0; i < n; i++) {
11
      long hash = 0;
12
      for (int j = i; j < n; j++) {
13
        hash = hash * PRIME + (text.charAt(j) - 'a' + 1);
14
        hash %= MOD;
15
        dp[i][j] = (int) hash;
16
      }
17
    }
18

19
    Set<Integer> set = new HashSet<>();
20
    int res = 0;
21
    for (int i = 0; i < n - 1; i++) {
22
      // compare text[i:j] with text[j+1: 2j-i+1]
23
      for (int j = i; 2 * j - i + 1 < n; j++) {
24
        if (dp[i][j] == dp[j + 1][2 * j - i + 1] && set.add(dp[i][j])) res++;
25
      }
26
    }
27

28
    return res;
29
  }
30
}