Distinct Subsequences II

Hard
890.

Distinct Subsequences II

Distinct Subsequences II is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var distinctSubseqII = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Distinct Subsequences II — Solution in Python, Java & C++

Distinct Subsequences II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Distinct Subsequences II is a hard coding problem on strings and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Distinct Subsequences II

  1. Hint 1

    Bucket the distinct subsequences by their last character — that is what makes duplicates collapse.

  2. Hint 2

    dp[c] is the number of distinct subsequences ending in letter c.

  3. Hint 3

    Appending the current character c to every existing subsequence (plus the empty one) overwrites dp[c] rather than adding to it.

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

  1. Keep dp[0 … 25], all starting at 0.
  2. For each character c, compute sum = 1 + Σ dp[j] — the 1 stands for the empty prefix, giving the single-character subsequence.
  3. Set dp[c] = sum (overwrite, not add).
  4. 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

Java

public static int distinctSubseqII(String s) {
    final int MOD = 1000000007;
    long[] dp = new long[26];
    for (int i = 0; i < s.length(); i++) {
        int c = s.charAt(i) - 'a';
        long sum = 1;
        for (int j = 0; j < 26; j++) sum = (sum + dp[j]) % MOD;
        dp[c] = sum;
    }
    long ans = 0;
    for (int j = 0; j < 26; j++) ans = (ans + dp[j]) % MOD;
    return (int) ans;
}

C++

int distinctSubseqII(string s) {
    const long long MOD = 1000000007LL;
    vector<long long> dp(26, 0);
    for (char ch : s) {
        int c = ch - 'a';
        long long sum = 1;
        for (int j = 0; j < 26; j++) sum = (sum + dp[j]) % MOD;
        dp[c] = sum;
    }
    long long ans = 0;
    for (int j = 0; j < 26; j++) ans = (ans + dp[j]) % MOD;
    return (int) ans;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming