Leetcode 115. Distinct Subsequences

Problem Explanation

Given two strings S and T, we want to find the number of distinct subsequences of S that equals T. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

For instance, let's take an example:

Input

S = "rabbbit", T = "rabbit"

Here, we want to find out how many times we can form the string "rabbit" from "rabbbit" by only removing characters while preserving the order.

Output

Output: 3

Explanation

Here, there are 3 ways we can generate "rabbit" from "rabbbit":

• rabbbit => _r_ab_b_b_it
• rabbbit => _ra_b_b_it
• rabbbit => _rab_b_it

We represent the selected characters with underscores (_).

Solution Approach

We can solve this by using a 2D dynamic programming table where dp[i][j] represents the number of distinct subsequences of T[0..j] in S[0..i]. We start by filling all dp[i][0] as 1 because an empty string will have exactly one subsequence in any string i.e., only one way to delete all characters in S.

To fill the rest of the table, we compute dp[i][j] as the sum of dp[i - 1][j] and dp[i - 1][j - 1] if s[i - 1] == t[j - 1] else dp[i][j] = dp[i - 1][j].

The solution to the problem will be the last cell of this table i.e., dp[m][n].

Java Solution

1
2java
3class Solution {
4 public int numDistinct(String s, String t) {
5    int m = s.length();
6    int n = t.length();
7    long[][] dp = new long[m+1][n+1];
8
9    for (int i = 0; i <= m; i++) dp[i][0] = 1;
10
11    for (int i = 1; i <= m; i++) 
12      for (int j = 1; j <= n; j++) 
13        if (s.charAt(i - 1) == t.charAt(j - 1)) 
14          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
15        else
16          dp[i][j] = dp[i - 1][j];
17      
18    return (int) dp[m][n];
19  }
20}

Python Solution

1
2python
3class Solution:
4    def numDistinct(self, s: str, t: str) -> int:
5        m, n = len(s), len(t)
6        dp = [[0] * (n+1) for _ in range(m+1)]
7
8        for i in range(m + 1):
9            dp[i][0] = 1
10            
11        for i in range(1, m + 1):
12            for j in range(1, n + 1):
13                if s[i-1] == t[j-1]:
14                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
15                else:
16                    dp[i][j] = dp[i - 1][j]
17                
18        return dp[-1][-1]

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int numDistinct(string s, string t) {
6    int m = s.size(), n = t.size();
7    vector<vector<long>> dp(m + 1, vector<long>(n + 1));
8    
9    for (int i = 0; i <= m; i++) dp[i][0] = 1;
10    
11    for (int i = 1; i <= m; i++) 
12      for (int j = 1; j <= n; j++) 
13        if (s[i - 1] == t[j - 1]) 
14          dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
15        else
16          dp[i][j] = dp[i - 1][j];
17      
18    return dp[m][n];
19  }
20};

C# Solution

1
2csharp
3public class Solution {
4    public int NumDistinct(string s, string t) {
5        int m = s.Length, n = t.Length;
6        long[,] dp = new long[m + 1, n + 1];
7        
8        for (int i = 0; i <= m; i++) dp[i,0] = 1;
9        
10        for (int i = 1; i <= m; i++) 
11            for (int j = 1; j <= n; j++) 
12                if (s[i - 1] == t[j - 1]) 
13                    dp[i,j] = dp[i - 1, j - 1] + dp[i - 1, j];
14                else
15                    dp[i,j] = dp[i - 1, j];
16        
17        return (int)dp[m,n];
18    }
19}

JavaScript Solution

1
2javascript
3var numDistinct = function(s, t) {
4    const m = s.length, n = t.length;
5    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
6    
7    for(let i = 0; i <= m; ++i) dp[i][0] = 1;
8    
9    for(let i = 1; i <= m; ++i) {
10        for(let j = 1; j <= n; ++j) {
11            if(s[i-1] === t[j-1]) {
12                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
13            } else {
14                dp[i][j] = dp[i - 1][j];
15            }
16        }
17    }
18    
19    return dp[m][n];
20};

As seen above, different solutions have been provided under different programming languages, namely Java, Python, C++, C#, and Javascript. These solutions share similar logic but are implemented using different syntaxes oriented towards the individual languages.

We can note that, in each solution, dynamic programming is used to solve the question. Dynamic programming allows us to build up a solution using the results of subproblems, and hence reduce the complexity of our algorithm.

The code first initializes a 2D array with the dimensions being the lengths of the two strings plus one. An extra cell is considered to handle the case when both strings are empty, in which case, there is one subsequence (an empty subsequence).

Our aim is to find the number of distinct subsequences of string T in string S. Hence, as we iterate over the lengths of both strings, we compare each character at the current positions. If they match, we increment the count of current subsequences by summing the count of subsequences of T[0..j-1] in S[0..i-1] and count of subsequences of T[0..j] in S[0..i-1]. However, if they don't match, we increment the count by the count of subsequences of T[0..j] in S[0..i-1].

Upon completion of the iterations, the final cell of the 2D array would hold the answer to the problem. The complexity of each solution remains O(MN), where M is the length of the first string and N is the length of the second string.

In conclusion, finding the number of distinct subsequences requires understanding of dynamic programming principles, and the solutions here can be implemented in various programming languages each offering a different syntax but maintaining the same logic flow.