Distinct Subsequences
Hard · Dynamic Programming · String · Dynamic Programming
Problem
Given two strings s and t, return how many different ways t can be spelled as a subsequence of s.
A subsequence keeps some characters of s in their original order and drops the rest. Two ways count as different when they use a different set of positions in s, even if they spell the same text.
The answer is guaranteed to fit in a 32-bit signed integer.
Examples
Input: s = "banana", t = "ban" Output: 3
The "b" is at position 0. The "a" and "n" can come from positions (1, 2), (1, 4) or (3, 4).
Input: s = "aaaa", t = "aa" Output: 6
Any 2 of the 4 positions spell "aa": 4 · 3 / 2 = 6 ways.
Input: s = "abc", t = "abcd" Output: 0
t has more characters than s, so it cannot be a subsequence.
Constraints
- 1 <= len(s), len(t) <= 1000
- s and t contain only English letters
- the answer fits in a 32-bit signed integer
Approaches
- Baseline: the full table over both suffixes — time O(n · m), space O(n · m)
Follow-up
The answer can be astronomically large for inputs that are not promised to fit (try s = 1,000 copies of "a" and t = 500 copies). The usual fix is to report it modulo 10^9 + 7; the recurrence is the same with % MOD after each addition. In a fixed-width language, additions that wrap around are harmless when the true final answer fits, because wrapping is arithmetic modulo 2^32.
Related problems
Start free on Cariara · Coding problems · System design studio
