Distinct Subsequences

in how many ways can you make string 2 using string 1

Distinct Subsequences

Problem

You are given two strings, s and t. Return the number of distinct subsequences of s that are equal to t.

A subsequence is a new string made by deleting some characters (or none) from the original string. The order of the remaining characters does not change.

The answer will always fit in a 32-bit signed integer.

Examples

Example 1

Input: s = "rabbbit", t = "rabbit"
Output: 3

• There are 3 ways to pick characters from s to build "rabbit".
• The three b letters in s give us 3 different choices for the two b letters in t.

Example 2

Input: s = "babgbag", t = "bag"
Output: 5

• There are 5 different ways to build "bag" from s.

Constraints

• 1 <= s.length, t.length <= 1000
• s and t contain only English letters.

Main Idea

We look at the last characters of both strings and ask one simple question: do they match?

• If they match, we have two choices:
  • Use this character. Then we move one step back in both s and t.
  • Skip this character in s. Then we move one step back in s only.
• If they do not match, we have only one choice:
  • Skip the character in s and move one step back in s.

We add the results of all choices to get the total count.

Base Cases

• If t is finished (empty), we found one valid way. Return 1.
• If s is finished but t is not, there is no way to build t. Return 0.

Solution 1: Recursion + Memoization (Top-Down)

In this method, we write a recursive function. We save each answer in a table, so we never solve the same problem twice.

var numDistinct = function (s, t) {
    let dp = Array.from({ length: s.length }, () => Array(t.length).fill(-1));

    function recurr(i, j) {
        // t is finished, so we found one valid way
        if (j < 0) return 1;

        // s is finished but t is not, so no way
        if (i < 0) return 0;

        // answer is already saved
        if (dp[i][j] !== -1) {
            return dp[i][j];
        }

        if (s[i] === t[j]) {
            // take it + skip it
            dp[i][j] = recurr(i - 1, j - 1) + recurr(i - 1, j);
        } else {
            // only skip it
            dp[i][j] = recurr(i - 1, j);
        }

        return dp[i][j];
    }

    return recurr(s.length - 1, t.length - 1);
};

Complexity

• Time Complexity: O(n * m)
  • n is the length of s and m is the length of t.
  • There are n * m different states, and each state is solved only once.
• Space Complexity: O(n * m)
  • The dp table stores n * m values.
  • The recursion stack also uses up to O(n + m) extra space, but O(n * m) is the bigger part.

Solution 2: Tabulation (Bottom-Up)

In this method, we do not use recursion. We build a table step by step, starting from the smallest problem.

Here, dp[i][j] means: the number of ways to build the first j characters of t from the first i characters of s.

function numDistinct(s, t) {
    const n = s.length;
    const m = t.length;

    // Create a DP table of size (n + 1) x (m + 1)
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // Base case: an empty t can be built in 1 way
    // (by deleting all characters from s)
    for (let i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }

    // Fill the table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s[i - 1] === t[j - 1]) {
                // characters match: take it + skip it
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                // characters do not match: only skip it
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][m];
}

Complexity

• Time Complexity: O(n * m)
  • We use two loops, one inside the other.
  • Each cell in the table is filled in constant time.
• Space Complexity: O(n * m)
  • The dp table has (n + 1) * (m + 1) cells.
  • There is no recursion stack, so this is slightly lighter than memoization.

Comparison

Summary

• The problem is solved with dynamic programming.
• At each step, we compare the last characters of s and t.
  • If they match, we add the "take" and "skip" results.
  • If they do not match, we only skip.
• Both solutions run in O(n * m) time and use O(n * m) space.
• Tabulation avoids recursion, so it is safer for long strings.