Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Hard

Distinct Subsequences

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.

Examples

Input:s = "rabbbit", t = "rabbit"
Output:3
As shown below, there are 3 ways you can generate "rabbit" from s. ra(b)bbit rab(b)it rabb(i)t
Input:s = "babgbag", t = "bag"
Output:5
As shown below, there are 5 ways you can generate "bag" from s. ba(b)g(bag) ba(bgba)g (bab)gb(a)g (ba)bgba(g) (babg)bag

Constraints

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

Dynamic Programming (2D Array)

Approach

### Intuition We need to find how many times string `t` appears as a subsequence in string `s`. This problem can be broken down into smaller subproblems. We can build a 2D dynamic programming table where `dp[i][j]` represents the number of distinct subsequences of `t[0...i-1]` in `s[0...j-1]`. ### Logic - If `t` is empty, it is a subsequence of any string `s` exactly 1 time (by deleting all characters of `s`). So `dp[0][j] = 1` for all `j`. - If `s` is empty and `t` is not, `t` cannot be a subsequence of `s`, so `dp[i][0] = 0` for all `i > 0`. - For a general state `dp[i][j]`: - We can always ignore the current character of `s` (which is `s[j-1]`). So we inherently have at least `dp[i][j-1]` ways to match `t[0...i-1]`. - If the current characters match (`t[i-1] == s[j-1]`), we can ALSO choose to use this character of `s` to match the current character of `t`. If we do, we need to know the number of ways to match the rest of `t` (`t[0...i-2]`) in the rest of `s` (`s[0...j-2]`), which is `dp[i-1][j-1]`. - Thus, if they match, `dp[i][j] = dp[i][j-1] + dp[i-1][j-1]`. Otherwise, `dp[i][j] = dp[i][j-1]`. ### Step-by-step - Initialize a 2D array `dp` of size `(t.length + 1) x (s.length + 1)` with 0s. - Set the first row to 1s: `dp[0][j] = 1` for all `j`. - Iterate through `i` from 1 to `t.length`. - Iterate through `j` from 1 to `s.length`. - If `t[i-1] == s[j-1]`, then `dp[i][j] = dp[i][j-1] + dp[i-1][j-1]`. - Else, `dp[i][j] = dp[i][j-1]`. - Return `dp[t.length][s.length]`.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

Time complexity is O(m * n) where m and n are the lengths of strings t and s respectively. Space complexity can be optimized to O(n) as we only need the previous row.

Solution.java
class Solution {    public int numDistinct(String s, String t) {        int m = t.length();        int n = s.length();                int[][] dp = new int[m + 1][n + 1];                // Empty t is a subsequence of any string 1 time        for (int j = 0; j <= n; j++) {            dp[0][j] = 1;        }                for (int i = 1; i <= m; i++) {            for (int j = 1; j <= n; j++) {                if (t.charAt(i - 1) == s.charAt(j - 1)) {                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];                } else {                    dp[i][j] = dp[i][j - 1];                }            }        }                return dp[m][n];    }}