Distinct Subsequences II LeetCode solution in Java

1
class Solution {
2
  public int distinctSubseqII(String s) {
3
    int mod = (int) 1e9 + 7;
4
    // For storing the last occurred index of a character.
5
    Integer li[] = new Integer[26];
6
    int n = s.length();
7
    int[] dp = new int[n + 1];
8
    // one empty string possible for a string of length 0.
9
    dp[0] = 1;
10
    char[] c = s.toCharArray();
11
    for (int i = 1; i <= n; i++) {
12
      // If the character is first occurred then 2 cases
13
      // Case 1 : we will not concat the character with previous subsequences
14
      // Case 2 : we will concat it.
15
      // Therefore, we multiply 2 with previous count.
16
      int curr = (2 * (dp[i - 1] % mod)) % mod;
17
      // Getting the int index from char for checking the previous occurrence in li[]
18
      int idx = c[i - 1] - 'a';
19
      // If previously occurred then we have to subtract the subsequences which are made
20
      // till li[idx-1] because they would be duplicated and counted twice unnecessarily
21
      if (li[idx] != null) dp[i] = (curr - dp[li[idx] - 1] + mod) % mod;
22
      else dp[i] = curr;
23
      li[idx] = i;
24
    }
25
    // Doing -1 because we don't have to count the empty string.
26
    return dp[n] - 1;
27
  }
28
}