Distinct Subsequences II LeetCode solution in C++

1
class Solution {
2
 public:
3
  int distinctSubseqII(string s) {
4
    int n = s.length();
5
    int mod = 1e9 + 7;
6

7
    vector<long long> dp(n + 1);
8
    unordered_map<char, int> mp;
9

10
    dp[0] = 1;
11
    for (int i = 1; i <= n; i++) {
12
      dp[i] = (2 * dp[i - 1]) % mod;
13
      char ch = s[i - 1];
14

15
      if (mp.find(ch) != mp.end()) {
16
        int j = mp[ch];
17
        dp[i] = (dp[i] - dp[j - 1] + mod) % mod;
18
      }
19
      mp[s[i - 1]] = i % mod;
20
    }
21
    return dp[n] - 1;
22
  }
23
};