Count Different Palindromic Subsequences LeetCode solution in Java

1
class Solution {
2
  public int countPalindromicSubsequences(String str) {
3
    int[] pre = new int[str.length()];
4
    HashMap<Character, Integer> map = new HashMap<>();
5
    int mod = 1000000007;
6
    for (int i = 0; i < str.length(); i++) {
7
      char ch = str.charAt(i);
8
      if (map.containsKey(ch)) pre[i] = map.get(ch);
9
      else pre[i] = -1;
10
      map.put(ch, i);
11
    }
12

13
    int[] next = new int[str.length()];
14
    map = new HashMap<>();
15
    for (int i = str.length() - 1; i >= 0; i--) {
16
      char ch = str.charAt(i);
17
      if (map.containsKey(ch)) next[i] = map.get(ch);
18
      else next[i] = Integer.MAX_VALUE;
19
      map.put(ch, i);
20
    }
21

22
    int[][] dp = new int[str.length()][str.length()];
23

24
    for (int g = 0; g < dp.length; g++) {
25
      for (int i = 0, j = g; j < dp[0].length; i++, j++) {
26
        if (g == 0) dp[i][j] = 1;
27
        else if (g == 1) dp[i][j] = 2;
28
        else {
29
          if (str.charAt(i) == str.charAt(j)) {
30
            int n = next[i];
31
            int p = pre[j];
32

33
            if (n > p) dp[i][j] = ((2 * dp[i + 1][j - 1]) + 2) % mod;
34
            else if (n == p) dp[i][j] = ((2 * dp[i + 1][j - 1]) + 1) % mod;
35
            else dp[i][j] = ((2 * dp[i + 1][j - 1]) - dp[n + 1][p - 1]) % mod;
36
          } else dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]) % mod;
37
        }
38
        if (dp[i][j] < 0) dp[i][j] += mod;
39
      }
40
    }
41
    return dp[0][dp[0].length - 1] % mod;
42
  }
43
}