115. Distinct Subsequences

Problem Overview

Count distinct subsequences of s that equal t.

Intuition

Count distinct subsequences of s that equal t. When characters match, you may use s[i] to extend t or skip it. When they differ, you must skip s[i]. A rolling array tracks how many ways exist for each prefix of t after scanning s.

Algorithm

1If t is longer than s, return 0.
2Let dp[j] be ways to form t[0..j-1] from the s prefix processed so far.
3Initialize dp[0] = 1 (empty subsequence).
4For each character of s, scan j from n down to 1.
5If s[i] equals t[j-1], add dp[j-1] to dp[j].
6Return dp[n].

Example Walkthrough

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

1.Extra b letters in s create extra choices at matching positions.
2.Each duplicate letter multiplies the number of valid pick sets.
3.Total distinct ways to spell rabbit is 3.

Output: 3

Common Pitfalls

•Iterate j right to left so dp[j-1] still refers to the previous row.
•On a match, add dp[j-1]; do not overwrite dp[j] with only that value.
•dp[0] stays 1 throughout because empty t is always formable.
•Use long if counts can overflow; here int fits LeetCode limits.

115.cs

// Approach: dp[j] = ways to form t[0..j-1] using processed prefix of s. When
// s[i] matches t[j-1], extend prior matches (dp[j-1]) or skip s[i] (dp[j]).
// Scan j right to left so dp[j-1] still holds the previous row.
// Complexity: O(m * n) time and O(n) extra space.
public class Solution
{
    public int NumDistinct(string s, string t)
    {
        int m = s.Length;
        int n = t.Length;
        if (n > m)
            return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;

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

        return dp[n];
    }
}

Was this solution helpful?