# Distinct Subsequences
**Difficulty:** HARD
[External](https://leetcode.com/problems/distinct-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/distinct-subsequences
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Coupang](https://scaleengineer.com/companies/coupang), [Salesforce](https://scaleengineer.com/companies/salesforce), [MathWorks](https://scaleengineer.com/companies/mathworks), [Trilogy](https://scaleengineer.com/companies/trilogy)
---
## Problem
Given two strings s and t, return _the number of distinct_ **_subsequences_** _of_ s _which equals_ t.

The test cases are generated so that 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.
`**rabb**b**it**`
`**ra**b**bbit**`
`**rab**b**bit**`

**Example 2:**

**Input:** s = "babgbag", t = "bag"
**Output:** 5
**Explanation:**
As shown below, there are 5 ways you can generate "bag" from s.
`**ba**b**g**bag`
`**ba**bgba**g**`
`**b**abgb**ag**`
`ba**b**gb**ag**`
`babg**bag**`

**Constraints:**

* `1 <= s.length, t.length <= 1000`
* `s` and `t` consist of English letters.

# Approaches
## Brute-Force Recursion
This approach uses a simple recursive function to solve the problem. The function `solve(i, j)` calculates the number of distinct subsequences of `s` starting from index `i` that match `t` starting from index `j`.
**Time:** O(2^m) · **Space:** O(m + n)
**Pros:** Simple and easy to understand the logic.; Direct translation of the problem's recursive definition.
**Cons:** Extremely inefficient due to a large number of overlapping subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for larger inputs.
### Explanation
The core idea is to explore all possibilities. For each character `s[i]` in the source string `s`, we compare it with the character `t[j]` in the target string `t`.

*   If `s[i]` matches `t[j]`, we have two choices:
    1.  We can use `s[i]` to form the subsequence. In this case, we need to find the number of ways to form the rest of `t` (i.e., `t[j+1:]`) from the rest of `s` (i.e., `s[i+1:]`).
    2.  We can skip `s[i]` and try to find a match for `t[j]` later in `s`. In this case, we need to find the number of ways to form `t[j:]` from `s[i+1:]`.
    The total number of ways is the sum of these two possibilities.

*   If `s[i]` does not match `t[j]`, we have no choice but to skip `s[i]` and try to find a match for `t[j]` in the rest of `s` (i.e., `s[i+1:]`).

This logic is implemented recursively. The base cases for the recursion are:
1.  If we have successfully matched all characters of `t` (i.e., `j` reaches the end of `t`), we have found one valid subsequence. We return 1.
2.  If we have run out of characters in `s` (i.e., `i` reaches the end of `s`) but still have characters in `t` to match, it's impossible to form the subsequence. We return 0.

```java
class Solution {
    public int numDistinct(String s, String t) {
        return solve(s, t, 0, 0);
    }

    private int solve(String s, String t, int i, int j) {
        // Base case 1: If we have found all characters of t, it's a valid subsequence.
        if (j == t.length()) {
            return 1;
        }
        // Base case 2: If we have run out of characters in s but not in t.
        if (i == s.length()) {
            return 0;
        }

        // If characters match, we have two options:
        // 1. Match s[i] with t[j] and look for the rest of t in the rest of s.
        // 2. Skip s[i] and look for t[j] in the rest of s.
        if (s.charAt(i) == t.charAt(j)) {
            return solve(s, t, i + 1, j + 1) + solve(s, t, i + 1, j);
        } else {
            // If characters don't match, we must skip s[i].
            return solve(s, t, i + 1, j);
        }
    }
}
```
### Algorithm
- Define a recursive function `solve(s, t, i, j)`.
- Base Case 1: If `j` equals the length of `t`, it means we have successfully formed `t`. Return 1.
- Base Case 2: If `i` equals the length of `s` but `j` is less than the length of `t`, it's impossible to form `t`. Return 0.
- If `s.charAt(i)` is equal to `t.charAt(j)`, the result is the sum of two recursive calls: `solve(s, t, i + 1, j + 1)` (matching the characters) and `solve(s, t, i + 1, j)` (skipping `s.charAt(i)`).
- If `s.charAt(i)` is not equal to `t.charAt(j)`, we must skip `s.charAt(i)`. The result is `solve(s, t, i + 1, j)`.

## Top-Down Dynamic Programming with Memoization
The brute-force recursive approach is slow because it repeatedly solves the same subproblems. We can optimize this by using memoization, a technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. This is a top-down dynamic programming approach.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Drastically improves performance by avoiding re-computation of subproblems.; Guaranteed to run in polynomial time.; Sufficiently efficient to pass the given constraints.
**Cons:** Requires O(m * n) space for the memoization table.; Still has the overhead associated with recursion (function call stack).
### Explanation
We use a 2D array, let's call it `memo`, to store the results of the subproblems. `memo[i][j]` will store the result of `solve(i, j)`. Before making a recursive call, we first check if the result for the current state `(i, j)` is already in our memoization table. If it is, we simply return the stored value. Otherwise, we compute the result as in the brute-force approach and store it in the table before returning.

This ensures that each subproblem `(i, j)` is solved only once. The number of unique subproblems is `m * n`, where `m` is the length of `s` and `n` is the length of `t`.

```java
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        // Use Integer to easily check for null (uncomputed states)
        Integer[][] memo = new Integer[m][n];
        return solve(s, t, 0, 0, memo);
    }

    private int solve(String s, String t, int i, int j, Integer[][] memo) {
        // Base case 1: Found a valid subsequence.
        if (j == t.length()) {
            return 1;
        }
        // Base case 2: Ran out of characters in s.
        if (i == s.length()) {
            return 0;
        }

        // Check memoization table
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        // If characters match, we have two options.
        if (s.charAt(i) == t.charAt(j)) {
            memo[i][j] = solve(s, t, i + 1, j + 1, memo) + solve(s, t, i + 1, j, memo);
        } else {
            // If characters don't match, we must skip s[i].
            memo[i][j] = solve(s, t, i + 1, j, memo);
        }

        return memo[i][j];
    }
}
```
### Algorithm
- Create a 2D array `memo` of size `s.length() x t.length()` to store results of subproblems, initialized to a value indicating 'not computed' (e.g., null or -1).
- Modify the recursive function `solve(s, t, i, j, memo)`.
- Inside the function, first check if `memo[i][j]` has been computed. If yes, return the stored value.
- If not, compute the result using the same recursive logic as the brute-force approach.
- Store the computed result in `memo[i][j]` before returning it.

## Bottom-Up Dynamic Programming (2D Array)
This approach is an iterative version of the memoized recursion, often called tabulation. We build the solution from the bottom up, starting with the smallest subproblems. We use a 2D DP table, where `dp[i][j]` represents the number of distinct subsequences of the prefix `s[0...i-1]` that equal the prefix `t[0...j-1]`.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** Avoids recursion overhead, making it slightly faster in practice than memoization.; The logic is systematic and easy to follow.
**Cons:** Requires O(m * n) space, which can be a limitation for very large strings.
### Explanation
We create a 2D array `dp` of size `(m+1) x (n+1)`. The extra row and column handle the base cases of empty strings.

**Initialization:**
*   `dp[i][0] = 1` for all `i` from 0 to `m`. This is because an empty string `t` is a subsequence of any string `s` in exactly one way (by deleting all characters of `s`).
*   `dp[0][j] = 0` for `j > 0`. A non-empty `t` cannot be a subsequence of an empty `s`.

**Transitions:**
We iterate through the strings `s` and `t` and fill the `dp` table. For each `dp[i][j]`, we consider the characters `s[i-1]` and `t[j-1]`.
*   If `s[i-1] != t[j-1]`, the character `s[i-1]` cannot be used to form the subsequence. So, the number of ways to form `t[0...j-1]` from `s[0...i-1]` is the same as forming it from `s[0...i-2]`. Thus, `dp[i][j] = dp[i-1][j]`.
*   If `s[i-1] == t[j-1]`, we have two sources for the count:
    1.  Ways to form `t[0...j-1]` from `s[0...i-2]` (i.e., not using `s[i-1]`). This is `dp[i-1][j]`.
    2.  Ways to form `t[0...j-2]` from `s[0...i-2]` (i.e., using `s[i-1]` to match `t[j-1]`). This is `dp[i-1][j-1]`.
    So, `dp[i][j] = dp[i-1][j] + dp[i-1][j-1]`.

The final answer is stored in `dp[m][n]`. We use `long` for the DP table to prevent potential overflow during intermediate additions, as the problem only guarantees the final answer fits in an `int`.

```java
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();

        // dp[i][j]: number of distinct subsequences of s[0..i-1] which equals t[0..j-1]
        long[][] dp = new long[m + 1][n + 1];

        // Base case: An empty t is a subsequence of any s in one way.
        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)) {
                    // Case 1: Match s[i-1] with t[j-1] -> dp[i-1][j-1]
                    // Case 2: Don't match s[i-1] with t[j-1] -> dp[i-1][j]
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // Must not match s[i-1]
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return (int) dp[m][n];
    }
}
```
### Algorithm
- Create a 2D DP table `dp` of size `(m+1) x (n+1)`, where `m=s.length()` and `n=t.length()`.
- Initialize the first column: `dp[i][0] = 1` for all `i`.
- Iterate with `i` from 1 to `m` and `j` from 1 to `n`.
- If `s.charAt(i-1) == t.charAt(j-1)`, set `dp[i][j] = dp[i-1][j] + dp[i-1][j-1]`.
- Otherwise, set `dp[i][j] = dp[i-1][j]`.
- The final answer is `dp[m][n]`.

## Space-Optimized Bottom-Up DP (1D Array)
This is the most efficient approach. By analyzing the transitions in the 2D DP approach, we notice that to compute the values for the current row `i`, we only need the values from the previous row `i-1`. This allows us to optimize the space complexity from O(m*n) to O(n) by using only a single 1D array.
**Time:** O(m * n) · **Space:** O(n)
**Pros:** Optimal space complexity of O(n).; Maintains the O(m * n) time efficiency.; Most efficient solution for this problem.
**Cons:** The logic, particularly the need for the backward inner loop, can be less intuitive to grasp initially compared to the 2D DP approach.
### Explanation
We can use a single 1D array, `dp`, of size `n+1`, where `dp[j]` will store the number of ways to form the prefix `t[0...j-1]`.

We iterate through the characters of `s` one by one (from `i = 1` to `m`). For each character `s[i-1]`, we update the `dp` array. The key insight is to iterate the inner loop (for `j`) backwards, from `n` down to `1`. This is crucial because when we calculate the new `dp[j]`, we need the *old* `dp[j]` (from the previous `s` character) and the *old* `dp[j-1]`. By iterating backwards, `dp[j-1]` still holds the value from the previous outer loop iteration when we use it to update `dp[j]`.

The transition `dp[i][j] = dp[i-1][j] + dp[i-1][j-1]` becomes `dp[j] = dp[j] + dp[j-1]` in the 1D array when `s[i-1] == t[j-1]`.

```java
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();

        // dp[j] will store the number of distinct subsequences of s's prefix
        // that equals t[0..j-1].
        long[] dp = new long[n + 1];

        // Base case: An empty t is a subsequence of any s in one way.
        dp[0] = 1;

        // Iterate through s
        for (int i = 1; i <= m; i++) {
            // Iterate through t backwards
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // dp[j] on the right is the count from the previous character of s (i-1).
                    // dp[j-1] is also the count from the previous character of s (i-1)
                    // because we are iterating j backwards.
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
        }

        return (int) dp[n];
    }
}
```
### Algorithm
- Create a 1D DP array `dp` of size `(n+1)`, where `n=t.length()`.
- Initialize `dp[0] = 1`.
- Iterate with an outer loop for `i` from 1 to `m` (for characters in `s`).
- Inside, iterate with an inner loop for `j` from `n` down to 1 (for characters in `t`).
- If `s.charAt(i-1) == t.charAt(j-1)`, update `dp[j]` by adding `dp[j-1]` to it: `dp[j] = dp[j] + dp[j-1]`.
- After the loops complete, `dp[n]` holds the final answer.

# Solutions
### Java

```java
class Solution {
public
  int numDistinct(String s, String t) {
    int n = t.length();
    int[] f = new int[n + 1];
    f[0] = 1;
    for (char a : s.toCharArray()) {
      for (int j = n; j > 0; --j) {
        char b = t.charAt(j - 1);
        if (a == b) {
          f[j] += f[j - 1];
        }
      }
    }
    return f[n];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numDistinct(string s, string t) {
    int n = t.size();
    unsigned long long f[n + 1];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (char &a : s) {
      for (int j = n; j; --j) {
        char b = t[j - 1];
        if (a == b) {
          f[j] += f[j - 1];
        }
      }
    }
    return f[n];
  }
};

```

### Python

```python
class Solution:
    def numDistinct(self, s: str, t: str) -> int: n = len(t) f = [1] + [0] * n for a in s: for j in range(n, 0, - 1): if a == t[j - 1]: f[j] += f[j - 1] return f[n]

```