Code : Distinct Subsequences II

class Solution {
  public:
    int distinctSubseqII(string s);
};

const int mod = (int)1e9 + 7;

int Solution ::distinctSubseqII(string str) {
    // dp[ch] is the number of distinct subsequences ending
    // at character ch.
    vector<int> dp(26);

    for (char ch : str) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += dp[i];
            sum %= mod;
        }
        // We discard all subsequences ending at last_occ[ch]
        // Hence, you don't see a +=
        dp[ch - 'a'] = (1 + sum) % mod;
    }

    int ans = 0;
    for (int i = 0; i < 26; i++) {
        ans += dp[i];
        ans %= mod;
    }
    return ans;
}