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.

1There 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.
2
3First, 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.
4
5Here is the pseudocode for this algorithm:
6
7initialize map with number of times each character appears in the string
8
9backtrack(subsequence, index):
10
11if index == string.length:
12
13if subsequence is distinct:
14
15add subsequence to list of distinct subsequences
16
17else:
18
19for i from index to string.length:
20
21backtrack(subsequence + string[i], i+1)