Distinct Subsequences | Problems

Given strings s and t, count the number of distinct subsequences of s which equal t.

Example: s = "rabbbit", t = "rabbit" → Output: 3

Sample Input

—

Sample Output

—

Constraints

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

Test Cases

Case 1

Args: ["rabbbit","rabbit"] Expected: 3

Case 2

Args: ["babgbag","bag"] Expected: 5

Topics

String Hash Table

DP

dp[i][j] = number of ways s[0..i-1] forms t[0..j-1].

function numDistinct(s, t) {
  const m = s.length, n = t.length;
  const dp = Array(n + 1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= m; i++) {
    for (let j = n; j >= 1; j--) {
      if (s[i-1] === t[j-1]) dp[j] += dp[j-1];
    }
  }
  return dp[n];
}

Time: O(mn) | Space: O(n)

Saved in this browser only. Private to you.