Distinct Subsequences

How it works

We want to count how many distinct subsequences of s equal t.

From the classic DP idea:

• dp[i][j] = number of ways to form t[j:] using s[i:]
• Transition:
  • always can skip s[i] -> dp[i+1][j]
  • if s[i] == t[j], we can also match them -> dp[i+1][j+1]

The space-optimized version uses a 1D array where dp[j] represents the values from the "next row" (i+1). But when updating dp[j] in-place, we still need access to the old value of dp[j+1] (which corresponds to dp[i+1][j+1]).

To solve this without an extra array, we carry that needed diagonal value using a single variable (prev), which always holds the correct "old dp[j+1]" for the current update.

Steps

1. Let m = len(s) and n = len(t).
2. Create a 1D array dp of size n + 1:
   • dp[j] represents the number of ways to form t[j:] using the suffix of s currently being processed
3. Initialize the base case:
   • dp[n] = 1 because there is exactly one way to form an empty t (choose nothing)
4. Iterate through s from right to left (from m - 1 down to 0):
   • Set prev = 1 which corresponds to the diagonal value dp[i+1][n] (always 1)
5. For each character s[i], iterate through t from right to left (from n - 1 down to 0):
   • Start with res = dp[j] (skipping s[i])
   • If s[i] == t[j], add prev (matching both characters)
   • Update prev to the old dp[j] before overwriting it (so it becomes the next diagonal)
   • Write dp[j] = res
6. After processing all characters, dp[0] contains the total number of distinct subsequences of s that equal t
7. Return dp[0]

Complexity

• Time complexity: O(m * n)
• Space complexity: O(n)

Where m is the length of the string s and n is the length of the string t.

Things to watch for

Confusing Subsequence with Substring

A subsequence allows skipping characters while maintaining order, whereas a substring requires consecutive characters. This problem counts subsequences, so you must consider both skipping and using each character in s, not just sliding windows of consecutive characters.

Incorrect Base Case for Empty Target

When the target string t is fully matched (j == len(t)), the function should return 1 (one valid way found), not 0. Returning 0 here would cause all paths to report no valid subsequences.

Forgetting to Always Include the Skip Option

At each position in s, you must always consider skipping the current character, regardless of whether it matches t[j]. A common mistake is only recursing when characters match, which misses valid subsequences that use later occurrences of the same character.

Integer Overflow in Large Inputs

The number of distinct subsequences can grow exponentially. In languages with fixed-size integers, the result may overflow. Some implementations use unsigned integers or modular arithmetic to handle this, depending on the problem constraints.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)

        dp[n] = 1
        for i in range(m - 1, -1, -1):
            prev = 1
            for j in range(n - 1, -1, -1):
                res = dp[j]
                if s[i] == t[j]:
                    res += prev

                prev = dp[j]
                dp[j] = res

        return dp[0]

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<uint> dp(n + 1, 0);
        dp[n] = 1;

        for (int i = m - 1; i >= 0; i--) {
            int prev = 1;
            for (int j = n - 1; j >= 0; j--) {
                uint res = dp[j];
                if (s[i] == t[j]) {
                    res += prev;
                }

                prev = dp[j];
                dp[j] = res;
            }
        }

        return dp[0];
    }
};