Count Subsequences

This question is part of my Career Advice series.

Original question: https://neetcode.io/problems/count-subsequences

1. Problem Breakdown:

The task is to determine the number of distinct subsequences of string s that are equal to string t. A subsequence is a sequence derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Clarifying Questions:

• Can the strings contain any characters other than lowercase English letters? (Given constraints suggest no, but it’s good to confirm).
• Are there any constraints on the length of s relative to t? (In this problem, s can be longer than t, but if t is longer than s, there are no valid subsequences).
• Should we consider case sensitivity? (Assuming yes based on standard string manipulation problems).

2. Core Data Structures and Algorithms:

• Dynamic Programming (DP): We’ll use a 2D DP table where dp[i][j] represents the number of distinct subsequences of s[0...i-1] that equal t[0...j-1].

3. Patterns to Remember:

• Subsequence Counting: This is a common dynamic programming pattern where you consider both including and excluding the current character in s when matching with t.
• DP Table Initialization: dp[i][0] should be 1 for all i because an empty string t can always be formed by any string s by deleting all characters.
• Recursive Subproblem: For each character in s, decide whether to match it with the current character in t or skip it.

4. Solution:

function numDistinct(s, t) {
  const m = s.length;
  const n = t.length;

  // DP table where dp[i][j] means number of subsequences in s[0..i-1] that match t[0..j-1]
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // Base case: An empty t can always be matched by any prefix of s by removing all characters
  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]) {
        // If characters match, count subsequences including and excluding current char
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      } else {
        // Otherwise, carry forward the count without including current char of s
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[m][n];
}

5. Explanation of Solution:

• Initialization: The DP table dp is initialized such that dp[i][0] is 1, indicating that any prefix of s can match an empty t.
• DP Transition:
  • If the current characters of s and t match (s[i-1] == t[j-1]), then we add the number of subsequences where:
    1. We include the current character from s in our match (dp[i-1][j-1]).
    2. We exclude the current character from s and just carry forward the previous count (dp[i-1][j]).
  • If they don’t match, we carry forward the previous count without including the current character of s.
• Result: The value at dp[m][n] gives the total number of distinct subsequences of s that match t.