Distinct Subsequences

Problem Statement

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

The test cases are generated so that the answer fits on a 32-bit signed integer.

Examples

Example 1:

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

Output: 3

Explanation: There are 3 ways to generate "rabbit" from "rabbbit":

• rabbbit
• rabbbit
• rabbbit

Example 2:

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

Output: 5

Explanation: There are 5 ways to generate "bag" from "babgbag":

• babgbag
• babgbag
• babgbag
• babgbag
• babgbag

Constraints

• 1 <= s.length, t.length <= 1000
• s and t consist of English letters

Approach

This problem is a classic 2D Dynamic Programming problem involving string matching and counting subsequences.

Intuition

The key insight is to build up the count of distinct subsequences by making a choice at each character:

1. Don't use the current character from s - inherit the count from the previous row
2. Use the current character from s (if it matches) - add the count from the diagonal

DP State Definition

dp[i][j] = number of distinct subsequences of s[0...i-1] that equal t[0...j-1]

Base Cases

• dp[i][0] = 1 for all i: An empty target string can be formed in exactly 1 way (by selecting nothing)
• dp[0][j] = 0 for all j > 0: An empty source cannot form a non-empty target

Recurrence Relation

For each position (i, j):

1. Always inherit from the previous row (don't use current character):

   dp[i][j] = dp[i-1][j]
   

2. If characters match s[i-1] == t[j-1], add the diagonal count (use current character):

   dp[i][j] += dp[i-1][j-1]
   

Algorithm Steps

1. Create a 2D DP table of size (m+1) × (n+1) where m = len(s), n = len(t)
2. Initialize base case: dp[i][0] = 1 for all i
3. For each position (i, j):
   • Set dp[i][j] = dp[i-1][j] (skip current character in s)
   • If s[i-1] == t[j-1], add dp[i-1][j-1] (use current character)
4. Return dp[m][n]

Complexity Analysis

Time Complexity: O(m × n)

• We fill a 2D table of size (m+1) × (n+1)
• Each cell requires O(1) work

Space Complexity: O(m × n)

• 2D DP table of size (m+1) × (n+1)
• Can be optimized to O(n) using 1D DP with right-to-left processing

Space Optimization

The space can be optimized to O(n) by using a 1D array and processing from right to left:

def numDistinct(s: str, t: str) -> int:
    n = len(t)
    dp = [0] * (n + 1)
    dp[0] = 1

    for char_s in s:
        for j in range(n, 0, -1):  # Right to left
            if char_s == t[j - 1]:
                dp[j] += dp[j - 1]

    return dp[n]

Processing right-to-left ensures we don't overwrite values we still need.

Key Insights

1. Two Choices: At each position, we can either use or skip the current character from s
2. Additive Counting: When characters match, we ADD the possibilities (not replace)
3. Order Matters: We process the DP table row by row to build up from smaller subproblems
4. Overflow Handling: Use long integers if needed for large counts

Common Pitfalls

1. Forgetting to inherit from previous row: Always start with dp[i][j] = dp[i-1][j]
2. Incorrect base case: Remember dp[i][0] = 1 (empty target has 1 way)
3. Off-by-one errors: Be careful with string indexing (s[i-1] for row i)
4. Space optimization direction: Must process right-to-left in 1D DP

Related Problems

• Edit Distance (LeetCode 72)
• Longest Common Subsequence (LeetCode 1143)
• Delete Operation for Two Strings (LeetCode 583)
• Minimum ASCII Delete Sum (LeetCode 712)

Tags

• Dynamic Programming
• String
• Hard