Solution For Distinct Subsequences

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.

Step by Step Implementation For Distinct Subsequences

class Solution {
    public int numDistinct(String s, String t) {
        // dp[i][j] means the number of distinct subsequences of t[0..i-1] in s[0..j-1]
        // dp[0][0] means the number of distinct subsequences of t[0..-1] in s[0..-1]
        // dp[i][0] means the number of distinct subsequences of t[0..i-1] in s[0..-1]
        // dp[0][j] means the number of distinct subsequences of t[0..-1] in s[0..j-1]
        int m = t.length(), n = s.length();
        int[][] dp = new int[m + 1][n + 1];
        // initialize dp[0][0] = 1
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            // initialize dp[i][0] = 0
            dp[i][0] = 0;
        }
        for (int j = 1; j <= n; j++) {
            // initialize dp[0][j] = 1
            dp[0][j] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    // if t[i-1] == s[j-1], then we can get dp[i][j] from dp[i-1][j-1] and dp[i][j-1]
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                } else {
                    // if t[i-1] != s[j-1], then we can only get dp[i][j] from dp[i][j-1]
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        // return dp[m][n]
        return dp[m][n];
    }
}

def numDistinct(s, t):
        # Base Case 
        if len(s) == 0: 
            return 0
    
        # Base Case 
        if len(t) == 0: 
            return 1
    
        # if the last characters of the two strings are same 
        if s[-1] == t[-1]: 
            return numDistinct(s[:-1], t[:-1]) + numDistinct(s[:-1], t) 
    
        # if the last characters of the two strings are not same 
        else: 
            return numDistinct(s[:-1], t)

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

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

It's 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.
(The caret symbol ^ means the chosen letters)

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.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

//Solution:

var numDistinct = function(s, t) {
    
    //Create a 2D array of s.length + 1 rows and t.length + 1 columns
    //This will represent our dynamic programming table
    let dp = new Array(s.length + 1).fill(0).map(() => new Array(t.length + 1).fill(0));
    
    //Fill the first row and first column with all zeros
    
    //The first row represents an empty string and the first column represents an empty substring
    //Therefore, there are no distinct subsequences
    
    //Fill the first row with all zeros
    for(let i = 0; i <= t.length; i++) {
        dp[0][i] = 0;
    }
    
    //Fill the first column with all zeros
    for(let i = 0; i <= s.length; i++) {
        dp[i][0] = 1;
    }
    
    //Now, we can fill the rest of the table
    
    //We iterate through each row (i), starting from the second row
    for(let i = 1; i <= s.length; i++) {
        
        //For each row, we iterate through each column (j), starting from the second column
        for(let j = 1; j <= t.length; j++) {
            
            //If the ith character of string s is equal to the jth character of string t
            //Then, the number of distinct subsequences will be the number of distinct subsequences of the substring s[0...i-1]
            //Plus, the number of distinct subsequences of the substring s[0...i-2]
            if(s.charAt(i-1) === t.charAt(j-1)) {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            }
            
            //If the ith character of string s is not equal to the jth character of string t
            //Then, the number of distinct subsequences will be the number of distinct subsequences of the substring s[0...i-2]
            else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    //The number of distinct subsequences will be stored in the last cell of the table
    //Which is located at dp[s.length][t.length]
    return dp[s.length][t.length];
};

There are many ways to solve this problem in C++. One approach is to use a map or unordered_map to keep track of the number of times each character appears in the string. Then, we can use a backtracking algorithm to generate all possible subsequences and check if they are distinct.

First, we initialize the map with the number of times each character appears in the string. Then, we use a backtracking algorithm to generate all possible subsequences. For each subsequence, we check if it is distinct by comparing it to all the other subsequences. If it is distinct, we add it to our list of distinct subsequences.

Here is the pseudocode for this algorithm:

initialize map with number of times each character appears in the string

backtrack(subsequence, index):

if index == string.length:

if subsequence is distinct:

add subsequence to list of distinct subsequences

else:

for i from index to string.length:

backtrack(subsequence + string[i], i+1)

public class Solution { 
    public int NumDistinct(string s, string t) {
        int[,] dp = new int[t.Length + 1, s.Length + 1];

        for (int i = 0; i <= s.Length; i++) {
            dp[0, i] = 1;
        }

        for (int i = 1; i <= t.Length; i++) {
            for (int j = 1; j <= s.Length; j++) {
                if (t[i - 1] == s[j - 1]) {
                    dp[i, j] = dp[i, j - 1] + dp[i - 1, j - 1];
                } else {
                    dp[i, j] = dp[i, j - 1];
                }
            }
        }

        return dp[t.Length, s.Length];
    }
}

/*

This is a dynamic programming problem. We can use a 2D array to keep track of the number of distinct subsequences for each prefix of the strings s and t. 

dp[i, j] will be the number of distinct subsequences of t[0..i-1] in s[0..j-1]. 

If s[j-1] != t[i-1], then we have dp[i, j] = dp[i, j-1], since we can't use s[j-1] to form a subsequence. 

If s[j-1] == t[i-1], then we have two options: we can use s[j-1] to form a subsequence, or we can ignore s[j-1]. 

If we use s[j-1], then the number of subsequences will be dp[i-1, j-1]. If we ignore s[j-1], then the number of subsequences will be dp[i, j-1]. Therefore, we have dp[i, j] = dp[i, j-1] + dp[i-1, j-1].

We can initialize dp[0, j] = 1 for all j, since the empty string is a subsequence of every string. 

The answer will be dp[t.Length, s.Length].

*/