> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/101-200/distinct-subsequences.md).

# 115. Distinct Subsequences

### Description

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.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/)
* [Leetcode](https://leetcode.com/problems/distinct-subsequences/)
* [ProgramCreek](https://www.programcreek.com/2013/01/leetcode-distinct-subsequences-total-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="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)

<div align="left"><img src="/files/-MG2EyexYt206N-KirXL" alt=""></div>
{% endtab %}

{% tab title="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)

<div align="left"><img src="/files/-MG2FJ5tMlPEXhrsU-L1" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(M*N) where M is the length of S and N is the length of T.
 * Space complexity : O(M*N) which is occupied by the 2D dp array that we create.
 */

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        return dp[m][n];
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(M*N) where M is the length of S and N is the length of T.
 * Space complexity : O(N) since we are using a single array which is the 
 *    size of the string T.
 */

class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[] dp = new int[n+1];
        dp[0] = 1;
        
        for(int i = 1; i <= m; i++) {
            for(int j = n; j > 0; j--) {
                if(s.charAt(i-1) == t.charAt(j-1)) {
                    dp[j] += dp[j-1];
                }
            }
        }
        
        return dp[n];
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*