Distinct Subsequences - Leetcode Solution

The Distinct Subsequences problem on LeetCode is a dynamic programming problem that asks to count the number of distinct subsequences of a string.

Problem Statement:

Given two strings s and t, return the number of distinct subsequences of s that are equal to t.

A subsequence of a string is a new string that is 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).

It is guaranteed the answer fits on a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from S. rabbbit rabbbit rabbbit Example 2:

Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from S. babgbag babgbag babgbag babgbag babgbag

Approach:

The problem can be solved by using dynamic programming. We can create a 2D array dp of size [n+1][m+1], where n is the length of string s and m is the length of string t. The element at dp[i][j] represents the number of distinct subsequences of s[0:i] that are equal to t[0:j].

The base conditions are:

1. dp[0][0] = 1, since an empty string can be matched with an empty string

2. dp[i][0] = 1, since an empty string can be matched with any non-empty string

3. dp[0][j] = 0, since a non-empty string cannot be matched with an empty string

The recurrence relation is as follows:

If s[i-1] == t[j-1], then we can either include or exclude the last character of s in the subsequence:

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

Here, dp[i-1][j] represents the number of times t is found in s[0:i-1] and dp[i-1][j-1] represents the number of times t is found in s[0:i-1] with the last character being s[i-1].

If s[i-1] != t[j-1], then we can only exclude the last character of s in the subsequence:

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

This is because we cannot include s[i-1] in the subsequence since it does not match t[j-1].

The final answer will be dp[n][m], where n and m are the lengths of s and t, respectively.

Time Complexity:

The time complexity of the solution is O(m*n), where m and n are the lengths of strings s and t, respectively.

Space Complexity:

The space complexity of the solution is O(m*n), since we are using a 2D array of size [n+1][m+1].

Code:

class Solution { public: int numDistinct(string s, string t) { int n = s.size(); int m = t.size();

    vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0));
    
    for(int i=0;i<=n;i++){
        dp[i][0] = 1;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i-1] == t[j-1]){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return dp[n][m];
}

};

The code is self-explanatory and easy to understand. It returns the number of distinct subsequences of s that are equal to t.

1