This question is part of my Career Advice series.

Original question: https://neetcode.io/problems/count-subsequences

The task is to determine the number of distinct subsequences of string `s`

that are equal to string `t`

. A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

**Clarifying Questions:**

- Can the strings contain any characters other than lowercase English letters? (Given constraints suggest no, but it’s good to confirm).
- Are there any constraints on the length of
`s`

relative to`t`

? (In this problem,`s`

can be longer than`t`

, but if`t`

is longer than`s`

, there are no valid subsequences). - Should we consider case sensitivity? (Assuming yes based on standard string manipulation problems).

**Dynamic Programming (DP):**We’ll use a 2D DP table where`dp[i][j]`

represents the number of distinct subsequences of`s[0...i-1]`

that equal`t[0...j-1]`

.

**Subsequence Counting:**This is a common dynamic programming pattern where you consider both including and excluding the current character in`s`

when matching with`t`

.**DP Table Initialization:**`dp[i][0]`

should be 1 for all`i`

because an empty string`t`

can always be formed by any string`s`

by deleting all characters.**Recursive Subproblem:**For each character in`s`

, decide whether to match it with the current character in`t`

or skip it.

```
function numDistinct(s, t) {
const m = s.length;
const n = t.length;
// DP table where dp[i][j] means number of subsequences in s[0..i-1] that match t[0..j-1]
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
// Base case: An empty t can always be matched by any prefix of s by removing all characters
for (let i = 0; i <= m; i++) {
dp[i][0] = 1;
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] === t[j - 1]) {
// If characters match, count subsequences including and excluding current char
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
// Otherwise, carry forward the count without including current char of s
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
```

**Initialization:**The DP table`dp`

is initialized such that`dp[i][0]`

is 1, indicating that any prefix of`s`

can match an empty`t`

.**DP Transition:**- If the current characters of
`s`

and`t`

match (`s[i-1] == t[j-1]`

), then we add the number of subsequences where:- We include the current character from
`s`

in our match (`dp[i-1][j-1]`

). - We exclude the current character from
`s`

and just carry forward the previous count (`dp[i-1][j]`

).

- We include the current character from
- If they don’t match, we carry forward the previous count without including the current character of
`s`

.

- If the current characters of
**Result:**The value at`dp[m][n]`

gives the total number of distinct subsequences of`s`

that match`t`

.