317. Distinct Subsequences II

Let dp[i] count the distinct subsequences (including the empty one) that can be formed from the first i characters. Appending the next character to every existing subsequence doubles the count, but that double-counts every subsequence the same character produced last time it appeared — subtract exactly that overlap.

Definition

Let dp[i] = the number of distinct subsequences (including the empty subsequence "") that can be built from the prefix s[:i].

Base case: dp[0] = 1 — from an empty prefix the only subsequence is the empty string.

Transition

Process character c = s[i-1]. Every distinct subsequence of s[:i-1] is still a distinct subsequence of s[:i] (we can skip c). We can also append c to each of those dp[i-1] subsequences, which would naively give 2 * dp[i-1].

But that over-counts. The subsequences produced by appending c this time exactly reproduce the ones we produced the last time we appended c. So we subtract that overlap:

dp[i] = 2 * dp[i-1] - last[c]

where last[c] = the value of dp that existed just before the previous occurrence of c was appended (i.e. the count that got doubled last time). If c never appeared, last[c] = 0 and nothing is subtracted. After computing dp[i], record last[c] = dp[i-1] for next time.

Everything is taken modulo 10^9 + 7; because of the subtraction, add MOD before the final % MOD to keep the result non-negative.

Worked example

s = "aba":

• dp[0] = 1 (just ""), last = {}.
• i=1, c='a': dp[1] = 2*1 - 0 = 2. Subsequences: "", "a". Set last['a'] = 1.
• i=2, c='b': dp[2] = 2*2 - 0 = 4. Subsequences: "", "a", "b", "ab". Set last['b'] = 2.
• i=3, c='a': dp[3] = 2*4 - last['a'] = 8 - 1 = 7. The 4 new "...a" strings would be "a", "aa", "ba", "aba", but "a" was already counted — subtracting last['a'] = 1 removes exactly that duplicate. Set last['a'] = 4.

dp[3] = 7 counts "", "a", "b", "ab", "aa", "ba", "aba".

Final answer

dp[n] includes the empty subsequence, which the problem excludes, so return dp[n] - 1 = 6.

Complexity

• Time: O(n) — one pass, O(1) work per character.
• Space: O(n) for the dp array (reducible to O(1) with a rolling scalar) plus O(26) for last.

class Solution {
    public int distinctSubseqII(String s) {
        int MOD = 1_000_000_007;
        long dp = 1;              // dp including the empty subsequence; dp[0] = 1
        long[] last = new long[26];
        for (int k = 0; k < s.length(); k++) {
            int c = s.charAt(k) - 'a';
            long prev = dp;
            dp = (2 * dp - last[c]) % MOD;
            if (dp < 0) dp += MOD;
            last[c] = prev;
        }
        return (int) ((dp - 1 + MOD) % MOD);
    }
}