Distinct subsequences

XXX. Distinct Subsequences

Dynamic Programming

String

Problem Statement:

Given two strings s and t, return the number of distinct subsequences of s which equals t. A subsequence of a string 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.

Algorithm:

1. Create a 2D array dp where dp[i][j] represents the number of ways to form the first i characters of t using the first j characters of s.
2. Initialize dp[0][j] = 1 for all j, since an empty t can be formed by any prefix of s.
3. Iterate over each character in t and s to fill the dp array:
• If t[i-1] == s[j-1], include both matching and non-matching cases: dp[i][j] = dp[i-1][j-1] + dp[i][j-1].
• If t[i-1] != s[j-1], carry forward the non-matching case: dp[i][j] = dp[i][j-1].
4. The result will be stored in dp[t.length()][s.length()].

Complexity:

Time Complexity: O(m * n), where m and n are the lengths of t and s respectively.
Space Complexity: O(m * n) for the dp table.

Java Implementation:

public int numDistinct(String s, String t) {
    // Create a 2D DP array with dimensions (t.length + 1) x (s.length + 1)
    int[][] dp = new int[t.length() + 1][s.length() + 1];

    // Base case: An empty t can be formed in exactly one way from any prefix of s
    for (int j = 0; j <= s.length(); j++)
        dp[0][j] = 1;

    // Fill the DP table
    for (int i = 1; i <= t.length(); i++) {
        for (int j = 1; j <= s.length(); j++) {
            if (t.charAt(i - 1) == s.charAt(j - 1)) {
                // If characters match, include both matching and non-matching cases
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            } else {
                // If characters don't match, carry forward the non-matching case
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    // The result is stored in the last cell of the table
    return dp[t.length()][s.length()];
}
                

Python Implementation:

def num_distinct(s: str, t: str) -> int:
    # Create a 2D DP array with dimensions (len(t) + 1) x (len(s) + 1)
    dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]

    # Base case: An empty t can be formed in exactly one way from any prefix of s
    for j in range(len(s) + 1):
        dp[0][j] = 1

    # Fill the DP table
    for i in range(1, len(t) + 1):
        for j in range(1, len(s) + 1):
            if t[i - 1] == s[j - 1]:
                # If characters match, include both matching and non-matching cases
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]
            else:
                # If characters don't match, carry forward the non-matching case
                dp[i][j] = dp[i][j - 1]

    # The result is stored in the last cell of the table
    return dp[len(t)][len(s)]
                

C++ Implementation:

#include 
#include 
using namespace std;

int numDistinct(string s, string t) {
    // Create a 2D DP array with dimensions (t.length() + 1) x (s.length() + 1)
    vector> dp(t.length() + 1, vector(s.length() + 1, 0));

    // Base case: An empty t can be formed in exactly one way from any prefix of s
    for (int j = 0; j <= s.length(); j++)
        dp[0][j] = 1;

    // Fill the DP table
    for (int i = 1; i <= t.length(); i++) {
        for (int j = 1; j <= s.length(); j++) {
            if (t[i - 1] == s[j - 1]) {
                // If characters match, include both matching and non-matching cases
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
            } else {
                // If characters don't match, carry forward the non-matching case
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    // The result is stored in the last cell of the table
    return dp[t.length()][s.length()];
}