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 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.

For example, "ACE" is a subsequence of "ABCDE" while "AEC" is not.

Approach:

1. Use a 2D dynamic programming (DP) table where dp[i][j] represents the number of distinct subsequences of the first j characters of s that equal the first i characters of t.
2. Initialize the first row of the DP table to 1, as an empty string t is a subsequence of any prefix of s.
3. Iterate through both strings, updating the DP table based on the following conditions:
   • If characters match, include both the match and skip options: dp[i][j] = dp[i-1][j-1] + dp[i][j-1].
   • If characters don't match, carry forward the previous value: dp[i][j] = dp[i][j-1].
4. The result is stored in dp[t.length()][s.length()].

Java Implementation:

// Function to count distinct subsequences of 's' matching 't'
public int numDistinct(String s, String t) {
    int[][] dp = new int[t.length() + 1][s.length() + 1];
    
    // Initialize the first row: empty 't' is a subsequence of any prefix of 's'
    for (int j = 0; j < dp[0].length; j++) 
        dp[0][j] = 1;

    // Fill the DP table row by row
    for (int i = 1; i < dp.length; i++) 
        for (int j = 1; j < dp[0].length; j++) 
            if (t.charAt(i - 1) == s.charAt(j - 1)) 
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; // Match and skip options
            else 
                dp[i][j] = dp[i][j - 1]; // Skip current character in 's'

    return dp[t.length()][s.length()];
}
        

Key Insights:

• **Dynamic Programming Table Setup:** The table tracks subsequences of increasing prefixes of s and t.
• **Base Case:** The first row is initialized to 1 because an empty t can always match any prefix of s.
• **Why Skip?:** If the current characters don't match, skipping the current character in s is necessary to find subsequences.
• **Match and Skip:** Matching characters increase the subsequence count by including both the match and skip options.

Complexity Analysis:

Time Complexity: O(m * n), where m is the length of t and n is the length of s.
Space Complexity: O(m * n), for the DP table.