Distinct Subsequences II — Hard Problem & Solution

Return the number of distinct non-empty subsequences of s, modulo 10^9 + 7.

Difficulty: Hard
Topics: Strings, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the number of distinct non-empty subsequences of s, modulo 10^9 + 7. Two subsequences are the same if they spell the same string, regardless of which indices produced them.

Example 1

Input: s = "abc"
Output: 7
Explanation: "a", "b", "c", "ab", "ac", "bc", "abc".

Example 2

Input: s = "aba"
Output: 6
Explanation: "a", "b", "ab", "aa", "ba", "aba".

Example 3

Input: s = "aaa"
Output: 3
Explanation: "a", "aa", "aaa".

Constraints

1 <= s.length <= 2000
s consists of lowercase English letters.

How to solve Distinct Subsequences II

Group distinct subsequences by last character. When a new occurrence of c arrives, the set of distinct subsequences ending in c becomes exactly 'everything so far, with c appended' — which replaces the old bucket instead of adding to it, and that replacement is precisely what removes the duplicates.

Approach

Keep dp[0 … 25], all starting at 0.
For each character c, compute sum = 1 + Σ dp[j] — the 1 stands for the empty prefix, giving the single-character subsequence.
Set dp[c] = sum (overwrite, not add).
The answer is Σ dp[j].

Why it works

Every distinct non-empty subsequence has exactly one last character, so the buckets partition the set and summing them counts each once. The overwrite is the key step: a subsequence ending in c could have been formed using an earlier c, and using the latest one instead gives the same string — so the newer bucket subsumes the older, and adding would double-count.

Complexity

Time — O(n · 26)
Space — O(1)

Pitfalls

Adding to dp[c] instead of overwriting counts the same string once per occurrence of its last character.
The + 1 inside the sum accounts for the one-character subsequence and is easy to drop.
Keep every addition under the modulo; the counts grow exponentially.

Reference solution

Python

def distinctSubseqII(s: str) -> int:
    MOD = 1000000007
    dp = [0] * 26
    for ch in s:
        c = ord(ch) - 97
        dp[c] = (1 + sum(dp)) % MOD
    return sum(dp) % MOD

JavaScript

var distinctSubseqII = function(s) {
    var MOD = 1000000007;
    var dp = [];
    for (var t = 0; t < 26; t++) dp.push(0);
    for (var i = 0; i < s.length; i++) {
        var c = s.charCodeAt(i) - 97;
        var sum = 1;
        for (var j = 0; j < 26; j++) sum = (sum + dp[j]) % MOD;
        dp[c] = sum;
    }
    var ans = 0;
    for (var j2 = 0; j2 < 26; j2++) ans = (ans + dp[j2]) % MOD;
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue