Code Implementation

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        # dp[i][j]: number of subsequences of s[0:i] equals t[0:j]
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        # An empty t can be formed by deleting all chars from s
        for i in range(m + 1):
            dp[i][0] = 1
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        return dp[m][n]
      

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));
        for (int i = 0; i <= m; ++i) dp[i][0] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
};
      

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        long[][] dp = new long[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return (int)dp[m][n];
    }
}
      

var numDistinct = function(s, t) {
    const m = s.length, n = t.length;
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) dp[i][0] = 1;
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[m][n];
};
      

Problem Description

Given two strings, s and t, determine how many distinct subsequences of s equal t. A subsequence is a sequence that can be derived from another string by deleting some (or no) characters, without changing the order of the remaining characters.

• You must count all possible ways to form t from s using this rule.
• Each character in s can be used at most once for each subsequence.
• Return the total number of distinct subsequences; the answer may be large, so use appropriate data types.

Example:
s = "rabbbit", t = "rabbit" → Output: 3

Thought Process

At first glance, you might consider generating every possible subsequence of s and checking which ones match t. However, since the number of subsequences grows exponentially with the length of s, this brute-force method is not practical for large inputs.

Instead, let's look for a smarter way. Notice that for each character in s, we can either use it (if it matches the current character in t) or skip it. This suggests a recursive or dynamic programming approach, where we break the problem into smaller subproblems: how many ways can we form the first j characters of t from the first i characters of s?

By thinking recursively and caching results (dynamic programming), we avoid recalculating the same subproblems and make our solution efficient.

Solution Approach

We use dynamic programming to solve this problem efficiently. Let's break down the steps:

1. Define Subproblems:
   • Let dp[i][j] be the number of distinct subsequences of s[0..i-1] that equals t[0..j-1].
2. Base Cases:
   • If t is empty (j == 0), there is exactly one subsequence (the empty subsequence) for any prefix of s: dp[i][0] = 1.
   • If s is empty (i == 0) and t is not, there are zero ways to form t: dp[0][j] = 0 for j > 0.
3. Recurrence Relation:
   • If s[i-1] == t[j-1], we have two choices:
     • Use s[i-1] to match t[j-1]: dp[i-1][j-1]
     • Skip s[i-1]: dp[i-1][j]
     • So, dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
   • If s[i-1] != t[j-1], we can only skip s[i-1]: dp[i][j] = dp[i-1][j]
4. Build the DP Table:
   • Iterate over i from 1 to m (len(s)), and j from 1 to n (len(t)), filling the table using the rules above.
5. Return the Result:
   • The answer is dp[m][n]: the number of ways to form all of t from all of s.

This approach is efficient because it avoids redundant calculations and only considers valid subsequences.

Example Walkthrough

Let's walk through the example: s = "rabbbit", t = "rabbit".

1. Initialization:
   • Create a DP table of size 8 x 7 (since s has length 7, t has length 6, and we add 1 for the empty string).
   • Set dp[i][0] = 1 for all i (empty t case).
2. Filling the Table:
   • For each character in s and t, apply the recurrence:
   • When s[i-1] == t[j-1] (e.g., the 'b's at positions 2, 3, 4 in s and position 2 in t), we add both choices.
   • Otherwise, carry over the value from above.
3. Result:
   • At the end, dp[7][6] (bottom-right cell) will be 3, meaning there are 3 distinct ways to form "rabbit" from "rabbbit".
4. Why 3?
   • The three ways correspond to using each of the three 'b's in s as the 'b' in t (with the other two skipped each time).

Time and Space Complexity

• Brute-Force Approach:
  • Would try all subsequences of s, which is 2^m (where m is the length of s).
  • For each, compare with t, so the overall time is exponential: O(2^m \cdot n).
• Optimized Dynamic Programming:
  • We fill a table of size (m+1) x (n+1), so time and space complexity are both O(mn).
  • Each cell is filled in constant time.
  • With further optimization, we can reduce space to O(n) by only keeping two rows.

Summary

The Distinct Subsequences problem asks us to count how many ways we can form one string as a subsequence of another. While a brute-force approach is infeasible, a dynamic programming solution allows us to build up the answer efficiently by considering subproblems and using optimal substructure. The key insight is recognizing when to use or skip characters, and how to translate that into a recurrence relation. By leveraging a DP table, we solve the problem in polynomial time, making it practical even for large strings.