Distinct Subsequences Hard 0 attempts
LeetCode ↗

Distinct Subsequences

Hard StringHash Table LeetCode

You're given two strings, s and t. Count how many distinct ways you can pick a subsequence from s (by deleting zero or more characters without reordering the rest) so that it exactly matches t.

Input Format
Implement numDistinct(s, t). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
s = "rabbbit"
t = "rabbit"
Output
3

Example 2

Input
s = "babgbag"
t = "bag"
Output
5
Constraints
  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters
  • The final answer fits in a signed 32-bit integer.
Test Cases (2)
Case 1
Args: ["rabbbit","rabbit"] Expected: 3
Case 2
Args: ["babgbag","bag"] Expected: 5
Topics
StringHash Table

DP

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

javascript
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.

JavaScript