Return the number of distinct subsequences of s that equal t.
Before you code
dp[i][j] counts the ways to form the first j characters of t from the first i of s. The last character of s's prefix is either used for t's last character (only if they match) or not used.
Hints
- dp[i][0] = 1: the empty t is formed one way.
dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if s[i-1] == t[j-1] else 0).- Counts can be large; the problem guarantees they fit in 32 bits.
Production & complexity notes
When solving Distinct subsequences on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Grids and strings to reinforce the underlying pattern.
What it practices
Counting with a two-string table, from Grids and strings.