04. Distinct Subsequences

Difficulty:HardPattern:Subsequence Count DPTime:O(s * t)Space:O(s * t)

Given two strings s and t, return the number of distinct subsequences of s which equals t.

How It Works & Algorithmic Design

Solves using 2D Subsequence Frequency Dynamic Programming:

DP Definition: dp[i][j] = number of distinct subsequences of s[0...i-1] that match t[0...j-1].
Base Case: dp[i][0] = 1 (an empty string t is a subsequence of any s prefix exactly once).
Transition:
- If s[i-1] === t[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (sum of matching character choice plus skipping character choice).
- Else: dp[i][j] = dp[i-1][j] (must skip s[i-1]).

Why This Approach Works Best

Evaluates total subsequence counts systematically in $O(|s| \times |t|)$ time and space.

Example Walkthrough

Input: s = "rabbbit", t = "rabbit"

Target subsequence matching.

Combinations: There are 3 distinct ways to drop one 'b' from "rabbbit" to leave "rabbit".

Subsequence count is 3.

Output: 3

3 distinct subsequences.

Answer: Distinct Subsequences DP implementation

function numDistinct(s, t) {
  const m = s.length, n = t.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  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]) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[m][n];
}

💡 Count matching subsequences by building dynamic programming table.

Key Takeaways

Base case empty target t gives dp[i][0] = 1.
Matching characters allow choice between including or skipping s[i-1].
Time complexity is $O(|s| \times |t|)$.