115. Distinct Subsequences - Explanation

Description

You are given two strings s and t, both consisting of english letters.

Return the number of distinct subsequences of s which are equal to t.

Example 1:

Input: s = "caaat", t = "cat"

Output: 3

Explanation: There are 3 ways you can generate "cat" from s.

(c)aa(at)
(c)a(a)a(t)
(ca)aa(t)

Example 2:

Input: s = "xxyxy", t = "xy"

Output: 5

Explanation: There are 5 ways you can generate "xy" from s.

(x)x(y)xy
(x)xyx(y)
x(x)(y)xy
x(x)yx(y)
xxy(x)(y)

Constraints:

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

Topics

String Dynamic Programming

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(m * n) time and O(m * n) space, where m is the length of the string s and n is the length of the string t.

Hint 1

Try to think in terms of recursion and visualize it as a decision tree, as we need to explore all subsequences of s. Can you determine the possible decisions at each recursion step?

Hint 2

We recursively iterate through the strings using indices i and j for s and t, respectively. At each recursion step, we can either skip the current character of s or include it in the current path if it matches the current character of t. Can you determine the base conditions for this recursive function?

Hint 3

If index j goes out of bounds, we return 1 as a valid subsequence is found. If index i goes out of bounds first, we return 0. At each recursion step, we return the sum of both paths. This approach is exponential. Can you think of a way to optimize it?

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant computations. A hash map or a 2D array can be used to store these results.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - Building solutions by breaking problems into smaller subproblems with base cases
Dynamic Programming - Using memoization or tabulation to avoid redundant computations
Subsequences - Understanding the difference between subsequences (non-contiguous) and substrings (contiguous)

1. Recursion

Intuition

This problem asks how many distinct subsequences of string s are equal to string t.

A subsequence is formed by deleting some characters from s without changing the order of the remaining characters.

At every position in s, we have a choice:

skip the current character in s
use the current character, but only if it matches the current character in t

The recursive function represents:
“How many ways can we form t[j:] using characters from s[i:]?”

If we successfully match all characters of t, we have found one valid subsequence.

Algorithm

If t is longer than s, return 0 immediately since it is impossible.
Define a recursive function dfs(i, j):
- i is the current index in s
- j is the current index in t
If j reaches the end of t:
- Return 1 because a valid subsequence has been formed
If i reaches the end of s before t is finished:
- Return 0 because no valid subsequence can be formed
Always consider skipping the current character in s:
- res = dfs(i + 1, j)
If s[i] == t[j]:
- Also consider using this character to match t[j]
- Add dfs(i + 1, j + 1) to res
Return the total count res
Start the recursion from (0, 0) and return the final result

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0

        def dfs(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0

            res = dfs(i + 1, j)
            if s[i] == t[j]:
                res += dfs(i + 1, j + 1)
            return res

        return dfs(0, 0)

public class Solution {
    public int numDistinct(String s, String t) {
        if (t.length() > s.length()) {
            return 0;
        }
        return dfs(s, t, 0, 0);
    }

    private int dfs(String s, String t, int i, int j) {
        if (j == t.length()) {
            return 1;
        }
        if (i == s.length()) {
            return 0;
        }

        int res = dfs(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            res += dfs(s, t, i + 1, j + 1);
        }
        return res;
    }
}

class Solution {
public:
    int numDistinct(string s, string t) {
        if (t.length() > s.length()) {
            return 0;
        }
        return dfs(s, t, 0, 0);
    }

private:
    int dfs(const string &s, const string &t, int i, int j) {
        if (j == t.length()) {
            return 1;
        }
        if (i == s.length()) {
            return 0;
        }

        int res = dfs(s, t, i + 1, j);
        if (s[i] == t[j]) {
            res += dfs(s, t, i + 1, j + 1);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {number}
     */
    numDistinct(s, t) {
        if (t.length > s.length) {
            return 0;
        }

        const dfs = (i, j) => {
            if (j === t.length) {
                return 1;
            }
            if (i === s.length) {
                return 0;
            }

            let res = dfs(i + 1, j);
            if (s[i] === t[j]) {
                res += dfs(i + 1, j + 1);
            }
            return res;
        };

        return dfs(0, 0);
    }
}

public class Solution {
    public int NumDistinct(string s, string t) {
        if (t.Length > s.Length) {
            return 0;
        }
        return Dfs(s, t, 0, 0);
    }

    private int Dfs(string s, string t, int i, int j) {
        if (j == t.Length) {
            return 1;
        }
        if (i == s.Length) {
            return 0;
        }

        int res = Dfs(s, t, i + 1, j);
        if (s[i] == t[j]) {
            res += Dfs(s, t, i + 1, j + 1);
        }
        return res;
    }
}

func numDistinct(s string, t string) int {
    if len(t) > len(s) {
        return 0
    }

    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if j == len(t) {
            return 1
        }
        if i == len(s) {
            return 0
        }

        res := dfs(i+1, j)
        if s[i] == t[j] {
            res += dfs(i+1, j+1)
        }
        return res
    }

    return dfs(0, 0)
}

class Solution {
    fun numDistinct(s: String, t: String): Int {
        if (t.length > s.length) return 0

        fun dfs(i: Int, j: Int): Int {
            if (j == t.length) return 1
            if (i == s.length) return 0

            var res = dfs(i + 1, j)
            if (s[i] == t[j]) {
                res += dfs(i + 1, j + 1)
            }
            return res
        }

        return dfs(0, 0)
    }
}

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        let sArray = Array(s), tArray = Array(t)
        let sLen = sArray.count, tLen = tArray.count
        if tLen > sLen { return 0 }

        func dfs(_ i: Int, _ j: Int) -> Int {
            if j == tLen { return 1 }
            if i == sLen { return 0 }

            var res = dfs(i + 1, j)
            if sArray[i] == tArray[j] {
                res += dfs(i + 1, j + 1)
            }
            return res
        }

        return dfs(0, 0)
    }
}

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        if t.len() > s.len() {
            return 0;
        }

        fn dfs(s: &[u8], t: &[u8], i: usize, j: usize) -> i32 {
            if j == t.len() {
                return 1;
            }
            if i == s.len() {
                return 0;
            }
            let mut res = dfs(s, t, i + 1, j);
            if s[i] == t[j] {
                res += dfs(s, t, i + 1, j + 1);
            }
            res
        }

        dfs(s, t, 0, 0)
    }
}

Time & Space Complexity

Time complexity: $O(2 ^ m)$
Space complexity: $O(m)$

Where $m$ is the length of the string $s$ .

2. Dynamic Programming (Top-Down)

Intuition

This problem asks us to count how many distinct subsequences of string s are equal to string t.

The recursive solution works by trying all possibilities, but it repeats the same subproblems many times. To make it efficient, we use top-down dynamic programming (memoization).

A state is uniquely identified by:

i: the current index in s
j: the current index in t

The recursive function answers the question:
“How many ways can we form t[j:] using characters from s[i:]?”

By storing the result for each (i, j) pair, we avoid recomputing the same state again and again.

Algorithm

If the length of t is greater than the length of s, return 0 since it is impossible to form t.
Create a memoization map dp where:
- the key is (i, j)
- the value is the number of ways to form t[j:] from s[i:]
Define a recursive function dfs(i, j):
- i represents the current position in s
- j represents the current position in t
If j reaches the end of t:
- Return 1 because a valid subsequence has been formed
If i reaches the end of s before t is fully matched:
- Return 0
If the state (i, j) is already in dp:
- Return the cached result
Always consider skipping the current character in s:
- res = dfs(i + 1, j)
If s[i] matches t[j]:
- Also consider using this character
- Add dfs(i + 1, j + 1) to res
Store res in dp[(i, j)] and return it
Start the recursion from (0, 0) and return the final result

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0

        dp = {}
        def dfs(i, j):
            if j == len(t):
                return 1
            if i == len(s):
                return 0
            if (i, j) in dp:
                return dp[(i, j)]

            res = dfs(i + 1, j)
            if s[i] == t[j]:
                res += dfs(i + 1, j + 1)
            dp[(i, j)] = res
            return res

        return dfs(0, 0)

public class Solution {
    private int[][] dp;

    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        if (n > m) return 0;
        dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(s, t, 0, 0);
    }

    private int dfs(String s, String t, int i, int j) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        int res = dfs(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            res += dfs(s, t, i + 1, j + 1);
        }
        dp[i][j] = res;
        return res;
    }
}

class Solution {
    vector<vector<int>> dp;
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        if (n > m) return 0;
        dp.assign(m + 1, vector<int>(n + 1, -1));
        return dfs(s, t, 0, 0);
    }

private:
    int dfs(const string &s, const string &t, int i, int j) {
        if (j == t.size()) return 1;
        if (i == s.size()) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        int res = dfs(s, t, i + 1, j);
        if (s[i] == t[j]) {
            res += dfs(s, t, i + 1, j + 1);
        }
        dp[i][j] = res;
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {number}
     */
    numDistinct(s, t) {
        let m = s.length,
            n = t.length;
        if (n > m) return 0;
        let dp = Array(m + 1)
            .fill()
            .map(() => Array(n + 1).fill(-1));

        const dfs = (i, j) => {
            if (j === n) return 1;
            if (i === m) return 0;
            if (dp[i][j] !== -1) return dp[i][j];

            let res = dfs(i + 1, j);
            if (s[i] === t[j]) {
                res += dfs(i + 1, j + 1);
            }
            dp[i][j] = res;
            return res;
        };

        return dfs(0, 0);
    }
}

public class Solution {
    private int?[,] dp;

    public int NumDistinct(string s, string t) {
        int m = s.Length, n = t.Length;
        if (n > m) return 0;
        dp = new int?[m + 1, n + 1];
        return Dfs(s, t, 0, 0);
    }

    private int Dfs(string s, string t, int i, int j) {
        if (j == t.Length) return 1;
        if (i == s.Length) return 0;
        if (dp[i, j].HasValue) return dp[i, j].Value;

        int res = Dfs(s, t, i + 1, j);
        if (s[i] == t[j]) {
            res += Dfs(s, t, i + 1, j + 1);
        }
        dp[i, j] = res;
        return res;
    }
}

class Solution {
    fun numDistinct(s: String, t: String): Int {
        if (t.length > s.length) return 0

        val dp = Array(s.length + 1) { IntArray(t.length + 1) { -1 } }

        fun dfs(i: Int, j: Int): Int {
            if (j == t.length) return 1
            if (i == s.length) return 0
            if (dp[i][j] != -1) return dp[i][j]

            var res = dfs(i + 1, j)
            if (s[i] == t[j]) {
                res += dfs(i + 1, j + 1)
            }

            dp[i][j] = res
            return res
        }

        return dfs(0, 0)
    }
}

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        let sArray = Array(s), tArray = Array(t)
        let sLen = sArray.count, tLen = tArray.count
        if tLen > sLen { return 0 }

        var dp = [[Int]: Int]()

        func dfs(_ i: Int, _ j: Int) -> Int {
            if j == tLen { return 1 }
            if i == sLen { return 0 }
            if let val = dp[[i, j]] { return val }

            var res = dfs(i + 1, j)
            if sArray[i] == tArray[j] {
                res += dfs(i + 1, j + 1)
            }
            dp[[i, j]] = res
            return res
        }

        return dfs(0, 0)
    }
}

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let m = s.len();
        let n = t.len();
        if n > m {
            return 0;
        }
        let mut dp = vec![vec![-1i32; n + 1]; m + 1];

        fn dfs(s: &[u8], t: &[u8], i: usize, j: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
            if j == t.len() {
                return 1;
            }
            if i == s.len() {
                return 0;
            }
            if dp[i][j] != -1 {
                return dp[i][j];
            }
            let mut res = dfs(s, t, i + 1, j, dp);
            if s[i] == t[j] {
                res += dfs(s, t, i + 1, j + 1, dp);
            }
            dp[i][j] = res;
            res
        }

        dfs(s, t, 0, 0, &mut dp)
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

3. Dynamic Programming (Bottom-Up)

Intuition

We want to count how many distinct subsequences of string s are equal to string t.

A subsequence is formed by deleting characters from s without changing the order.
So for every character in s, we have a choice:

skip it
use it (only if it matches the current character in t)

Instead of solving this recursively, we use bottom-up dynamic programming by building answers for smaller suffixes first.

We define a DP state that answers:
“How many ways can we form t[j:] using s[i:]?”

By filling a DP table from the end of the strings toward the beginning, we ensure that all required subproblems are already solved.

Algorithm

Let m = len(s) and n = len(t).
Create a 2D DP table dp of size (m + 1) x (n + 1):
- dp[i][j] represents the number of ways to form t[j:] from s[i:]
Initialize the base case:
- For all i, set dp[i][n] = 1
- This means there is exactly one way to form an empty string t (by choosing nothing)
Fill the table from bottom to top and right to left:
For each position (i, j):
- Always consider skipping s[i]:
  - dp[i][j] = dp[i + 1][j]
- If s[i] == t[j]:
  - Also consider using s[i] to match t[j]
  - Add dp[i + 1][j + 1] to dp[i][j]
After filling the table, dp[0][0] contains the total number of distinct subsequences
Return dp[0][0]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = dp[i + 1][j]
                if s[i] == t[j]:
                    dp[i][j] += dp[i + 1][j + 1]

        return dp[0][0]

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.length(), n = t.length();
        vector<vector<uint>> dp(m + 1, vector<uint>(n + 1, 0));

        for (int i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (s[i] == t[j]) {
                    dp[i][j] += dp[i + 1][j + 1];
                }
            }
        }

        return dp[0][0];
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {number}
     */
    numDistinct(s, t) {
        let m = s.length,
            n = t.length;
        let dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

        for (let i = 0; i <= m; i++) {
            dp[i][n] = 1;
        }

        for (let i = m - 1; i >= 0; i--) {
            for (let j = n - 1; j >= 0; j--) {
                dp[i][j] = dp[i + 1][j];
                if (s[i] === t[j]) {
                    dp[i][j] += dp[i + 1][j + 1];
                }
            }
        }

        return dp[0][0];
    }
}

public 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, n] = 1;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i, j] = dp[i + 1, j];
                if (s[i] == t[j]) {
                    dp[i, j] += dp[i + 1, j + 1];
                }
            }
        }

        return dp[0, 0];
    }
}

class Solution {
    fun numDistinct(s: String, t: String): Int {
        val m = s.length
        val n = t.length
        val dp = Array(m + 1) { IntArray(n + 1) }

        for (i in 0..m) {
            dp[i][n] = 1
        }

        for (i in m - 1 downTo 0) {
            for (j in n - 1 downTo 0) {
                dp[i][j] = dp[i + 1][j]
                if (s[i] == t[j]) {
                    dp[i][j] += dp[i + 1][j + 1]
                }
            }
        }

        return dp[0][0]
    }
}

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        let m = s.count, n = t.count
        var dp = Array(
            repeating: Array(repeating: 0, count: n + 1),
            count: m + 1
        )

        let sArray = Array(s)
        let tArray = Array(t)

        for i in 0...m {
            dp[i][n] = 1
        }

        for i in stride(from: m - 1, through: 0, by: -1) {
            for j in stride(from: n - 1, through: 0, by: -1) {
                let base = dp[i + 1][j]
                dp[i][j] = base
                if sArray[i] == tArray[j] {
                    let addend = dp[i + 1][j + 1]
                    if base > Int.max - addend {
                        dp[i][j] = 0
                    } else {
                        dp[i][j] += addend
                    }
                }
            }
        }

        return dp[0][0]
    }
}

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let m = s.len();
        let n = t.len();
        let mut dp = vec![vec![0i32; n + 1]; m + 1];

        for i in 0..=m {
            dp[i][n] = 1;
        }

        for i in (0..m).rev() {
            for j in (0..n).rev() {
                dp[i][j] = dp[i + 1][j];
                if s[i] == t[j] {
                    dp[i][j] += dp[i + 1][j + 1];
                }
            }
        }

        dp[0][0]
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

4. Dynamic Programming (Space Optimized)

Intuition

We want to count how many distinct subsequences of string s are equal to string t.

From the bottom-up DP approach, we know that:

dp[i][j] depends only on values from the next row (i + 1)
we never need older rows once a new row is computed

This means we can optimize space by keeping only two 1D arrays:

one representing results for i + 1
one representing results for the current i

The key idea stays the same:
At each position, we can either:

skip the current character in s
or use it if it matches the current character in t

Algorithm

Let m = len(s) and n = len(t).
Create two 1D arrays of size n + 1:
- dp represents results for the next row (i + 1)
- nextDp represents results for the current row (i)
Initialize the base case:
- Set dp[n] = 1 and nextDp[n] = 1
- There is exactly one way to form an empty t
Iterate over string s from right to left:
For each index i, iterate over string t from right to left:
- Always carry over the value from skipping s[i]:
  - nextDp[j] = dp[j]
- If s[i] == t[j]:
  - Add the number of ways from matching both characters:
    - nextDp[j] += dp[j + 1]
After finishing the row, copy nextDp into dp
After processing all characters, dp[0] contains the total number of distinct subsequences
Return dp[0]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)
        nextDp = [0] * (n + 1)

        dp[n] = nextDp[n] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                nextDp[j] = dp[j]
                if s[i] == t[j]:
                    nextDp[j] += dp[j + 1]
            dp = nextDp[:]

        return dp[0]

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[] dp = new int[n + 1];
        int[] nextDp = new int[n + 1];

        dp[n] = nextDp[n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                nextDp[j] = dp[j];
                if (s.charAt(i) == t.charAt(j)) {
                    nextDp[j] += dp[j + 1];
                }
            }
            dp = nextDp.clone();
        }

        return dp[0];
    }
}

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<uint> dp(n + 1, 0);
        vector<uint> nextDp(n + 1, 0);
        dp[n] = nextDp[n] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                nextDp[j] = dp[j];
                if (s[i] == t[j]) {
                    nextDp[j] += dp[j + 1];
                }
            }
            dp = nextDp;
        }

        return dp[0];
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {number}
     */
    numDistinct(s, t) {
        let m = s.length,
            n = t.length;
        let dp = new Array(n + 1).fill(0);
        let nextDp = new Array(n + 1).fill(0);

        dp[n] = nextDp[n] = 1;
        for (let i = m - 1; i >= 0; i--) {
            for (let j = n - 1; j >= 0; j--) {
                nextDp[j] = dp[j];
                if (s[i] === t[j]) {
                    nextDp[j] += dp[j + 1];
                }
            }
            dp = nextDp.slice();
        }

        return dp[0];
    }
}

public class Solution {
    public int NumDistinct(string s, string t) {
        int m = s.Length, n = t.Length;
        int[] dp = new int[n + 1];
        int[] nextDp = new int[n + 1];

        dp[n] = nextDp[n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                nextDp[j] = dp[j];
                if (s[i] == t[j]) {
                    nextDp[j] += dp[j + 1];
                }
            }
            dp = (int[])nextDp.Clone();
        }

        return dp[0];
    }
}

class Solution {
    fun numDistinct(s: String, t: String): Int {
        val m = s.length
        val n = t.length
        var dp = IntArray(n + 1)
        var nextDp = IntArray(n + 1)

        dp[n] = 1
        nextDp[n] = 1

        for (i in m - 1 downTo 0) {
            for (j in n - 1 downTo 0) {
                nextDp[j] = dp[j]
                if (s[i] == t[j]) {
                    nextDp[j] += dp[j + 1]
                }
            }
            dp = nextDp.copyOf()
        }

        return dp[0]
    }
}

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        let m = s.count, n = t.count
        var dp = [Int](repeating: 0, count: n + 1)
        var nextDp = [Int](repeating: 0, count: n + 1)
        dp[n] = 1
        nextDp[n] = 1

        let sArr = Array(s)
        let tArr = Array(t)

        for i in stride(from: m - 1, through: 0, by: -1) {
            for j in stride(from: n - 1, through: 0, by: -1) {
                nextDp[j] = dp[j]
                if sArr[i] == tArr[j] {
                    let addend = dp[j + 1]
                    if nextDp[j] > Int.max - addend {
                        nextDp[j] = 0
                    } else {
                        nextDp[j] += addend
                    }
                }
            }
            dp = nextDp
        }

        return dp[0]
    }
}

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let m = s.len();
        let n = t.len();
        let mut dp = vec![0i32; n + 1];
        let mut next_dp = vec![0i32; n + 1];
        dp[n] = 1;
        next_dp[n] = 1;

        for i in (0..m).rev() {
            for j in (0..n).rev() {
                next_dp[j] = dp[j];
                if s[i] == t[j] {
                    next_dp[j] += dp[j + 1];
                }
            }
            dp = next_dp.clone();
        }

        dp[0]
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

5. Dynamic Programming (Optimal)

Intuition

We want to count how many distinct subsequences of s equal t.

From the classic DP idea:

dp[i][j] = number of ways to form t[j:] using s[i:]
Transition:
- always can skip s[i] -> dp[i+1][j]
- if s[i] == t[j], we can also match them -> dp[i+1][j+1]

The space-optimized version uses a 1D array where dp[j] represents the values from the "next row" (i+1).
But when updating dp[j] in-place, we still need access to the old value of dp[j+1] (which corresponds to dp[i+1][j+1]).

To solve this without an extra array, we carry that needed diagonal value using a single variable (prev), which always holds the correct "old dp[j+1]" for the current update.

Algorithm

Let m = len(s) and n = len(t).
Create a 1D array dp of size n + 1:
- dp[j] represents the number of ways to form t[j:] using the suffix of s currently being processed
Initialize the base case:
- dp[n] = 1 because there is exactly one way to form an empty t (choose nothing)
Iterate through s from right to left (from m - 1 down to 0):
- Set prev = 1 which corresponds to the diagonal value dp[i+1][n] (always 1)
For each character s[i], iterate through t from right to left (from n - 1 down to 0):
- Start with res = dp[j] (skipping s[i])
- If s[i] == t[j], add prev (matching both characters)
- Update prev to the old dp[j] before overwriting it (so it becomes the next diagonal)
- Write dp[j] = res
After processing all characters, dp[0] contains the total number of distinct subsequences of s that equal t
Return dp[0]

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)

        dp[n] = 1
        for i in range(m - 1, -1, -1):
            prev = 1
            for j in range(n - 1, -1, -1):
                res = dp[j]
                if s[i] == t[j]:
                    res += prev

                prev = dp[j]
                dp[j] = res

        return dp[0]

public class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[] dp = new int[n + 1];

        dp[n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            int prev = 1;
            for (int j = n - 1; j >= 0; j--) {
                int res = dp[j];
                if (s.charAt(i) == t.charAt(j)) {
                    res += prev;
                }

                prev = dp[j];
                dp[j] = res;
            }
        }

        return dp[0];
    }
}

class Solution {
    /**
     * @param {string} s
     * @param {string} t
     * @return {number}
     */
    numDistinct(s, t) {
        let m = s.length,
            n = t.length;
        let dp = new Array(n + 1).fill(0);

        dp[n] = 1;
        for (let i = m - 1; i >= 0; i--) {
            let prev = 1;
            for (let j = n - 1; j >= 0; j--) {
                let res = dp[j];
                if (s[i] === t[j]) {
                    res += prev;
                }

                prev = dp[j];
                dp[j] = res;
            }
        }

        return dp[0];
    }
}

public class Solution {
    public int NumDistinct(string s, string t) {
        int m = s.Length, n = t.Length;
        int[] dp = new int[n + 1];

        dp[n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            int prev = 1;
            for (int j = n - 1; j >= 0; j--) {
                int res = dp[j];
                if (s[i] == t[j]) {
                    res += prev;
                }

                prev = dp[j];
                dp[j] = res;
            }
        }

        return dp[0];
    }
}

class Solution {
    fun numDistinct(s: String, t: String): Int {
        val m = s.length
        val n = t.length
        val dp = IntArray(n + 1)

        dp[n] = 1
        for (i in m - 1 downTo 0) {
            var prev = 1
            for (j in n - 1 downTo 0) {
                var res = dp[j]
                if (s[i] == t[j]) {
                    res += prev
                }
                prev = dp[j]
                dp[j] = res
            }
        }

        return dp[0]
    }
}

class Solution {
    func numDistinct(_ s: String, _ t: String) -> Int {
        let m = s.count, n = t.count
        var dp = [Int](repeating: 0, count: n + 1)
        dp[n] = 1
        let sArr = Array(s)
        let tArr = Array(t)

        for i in stride(from: m - 1, through: 0, by: -1) {
            var prev = 1
            for j in stride(from: n - 1, through: 0, by: -1) {
                let base = dp[j]
                var res = base
                if sArr[i] == tArr[j] {
                    if base > Int.max - prev {
                        res = 0
                    } else {
                        res += prev
                    }
                }
                prev = dp[j]
                dp[j] = res
            }
        }

        return dp[0]
    }
}

impl Solution {
    pub fn num_distinct(s: String, t: String) -> i32 {
        let s = s.as_bytes();
        let t = t.as_bytes();
        let m = s.len();
        let n = t.len();
        let mut dp = vec![0i32; n + 1];
        dp[n] = 1;

        for i in (0..m).rev() {
            let mut prev = 1;
            for j in (0..n).rev() {
                let mut res = dp[j];
                if s[i] == t[j] {
                    res += prev;
                }
                prev = dp[j];
                dp[j] = res;
            }
        }

        dp[0]
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the length of the string $s$ and $n$ is the length of the string $t$ .

Common Pitfalls

Confusing Subsequence with Substring

A subsequence allows skipping characters while maintaining order, whereas a substring requires consecutive characters. This problem counts subsequences, so you must consider both skipping and using each character in s, not just sliding windows of consecutive characters.

Incorrect Base Case for Empty Target

When the target string t is fully matched (j == len(t)), the function should return 1 (one valid way found), not 0. Returning 0 here would cause all paths to report no valid subsequences.

# Wrong: Returns 0 when target is matched
if j == len(t):
    return 0

# Correct: Successfully formed one subsequence
if j == len(t):
    return 1

Forgetting to Always Include the Skip Option

At each position in s, you must always consider skipping the current character, regardless of whether it matches t[j]. A common mistake is only recursing when characters match, which misses valid subsequences that use later occurrences of the same character.

# Wrong: Only recurses on match
if s[i] == t[j]:
    return dfs(i + 1, j + 1)

# Correct: Always skip, optionally match
res = dfs(i + 1, j)  # Always include skip
if s[i] == t[j]:
    res += dfs(i + 1, j + 1)  # Add match option

Integer Overflow in Large Inputs

The number of distinct subsequences can grow exponentially. In languages with fixed-size integers, the result may overflow. Some implementations use unsigned integers or modular arithmetic to handle this, depending on the problem constraints.