Distinct Subsequences

Problem in Plain English

Given a source string and a target string, count how many different ways the target appears as a subsequence of the source, where each way deletes characters while keeping the remaining order.

Problem Statement

Given two strings s and t, return the number of distinct subsequences of s that equal t. A subsequence keeps the relative order of its characters while deleting zero or more characters from the original string.

Two ways are different when they use different index positions in s, even if the matched letters look the same. For example, the three b characters in "rabbbit" create separate ways to match the b characters of "rabbit".

The answer is guaranteed to fit in a 32-bit signed integer.

Constraints

1 <= s.length <= 1000
1 <= t.length <= 1000
s and t consist of English letters.
The answer fits in a 32-bit signed integer.

Examples

Example 1

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

Use source positions 0 and 1 for r and a, positions 5 and 6 for i and t, then choose b positions (2,3), (2,4), or (3,4). Each increasing index list spells rabbit; these are three distinct embeddings even though their letters coincide.

Example 2

Input: s = "babgbag", t = "bag"
Output: 5

Using zero-based indices, the five embeddings are (0,1,3), (0,1,6), (0,5,6), (2,5,6), and (4,5,6). Every triple spells bag and respects source order.

Example 3

Input: s = "a", t = "aa"
Output: 0

One source position cannot supply two target characters. Equal letter values do not permit reusing the same index, so a longer target has no embedding.

Intuition

Count choices of source positions, not different spellings. In "rabbbit", choosing any two of the three b positions leaves "rabbit", giving three embeddings. At a source character, skipping it keeps the next target character unchanged; using it advances the target only when the letters match. These disjoint choices add counts. Dynamic programming remembers the number of ways to form each target prefix rather than exploring the same remaining strings repeatedly.

Approaches

Recursive Match or Skip

Solution Details

Reveal Recursive Match or Skip: intuition, complexity, and code

Intuition

Enumerate whether each source position is skipped or used for the next target character. A match allows both choices; a mismatch allows only skipping. Define dfs(i,j) as the number of embeddings of the target suffix starting at j inside the source suffix starting at i. Different paths can reach the same pair, which explains the exponential repetition.

Step-by-Step Logic

Start dfs(0,0); i and j are zero-based positions in the source and target. In Example 1 r matches r, so explore dfs(1,1) for use and dfs(1,0) for skip.
If the target is exhausted, return 1: choosing no more positions is one completed embedding. If the source is exhausted first, return 0. Check target exhaustion first so exhausting both succeeds.
At any mismatch, advance only i. At a match, add dfs(i+1,j+1) and dfs(i+1,j), because using and skipping the current source index are different choices. At (2,2), the first b has use count 2 and skip count 1.
Return the sum through the outer a and r matches. Their skip branches contribute 0, so Example 1 returns 3. Cap each sum at 2147483647 to retain correctness without overflow; the final count is guaranteed not to exceed that cap.

Why It Works

Every embedding either contains source index i or does not. The containing group exists only if s[i] equals t[j], and removing that matched pair bijects it with embeddings counted by dfs(i+1,j+1). The other group is exactly dfs(i+1,j). The groups are disjoint and exhaustive, so their sum counts every increasing index choice once. The empty target has one completion and a nonempty target with empty source has none. Induction on remaining source length proves the recurrence. For nonnegative counts, min(C,min(C,x)+min(C,y)) equals min(C,x+y); therefore propagating capped counts computes the true result capped at C. The promised final answer is at most C, so it is unchanged.

Dry Run

Recursive Match or Skip: variable states at each step
State (i,j)	s[i]	t[j]	Dependencies / terminal rule	Return count
(7,6)	end	end	target exhausted: one completed embedding	1
(7,5)	end	t	source exhausted before target	0
(6,5)	t	t	use (7,6) = 1; skip (7,5) = 0; sum 1+0	1
(7,4)	end	i	source exhausted before target	0
(6,4)	t	i	mismatch; skip (7,4) = 0	0
(5,4)	i	i	use (6,5) = 1; skip (6,4) = 0; sum 1+0	1
(4,4)	b	i	mismatch; skip (5,4) = 1	1
(7,3)	end	b	source exhausted before target	0
(6,3)	t	b	mismatch; skip (7,3) = 0	0
(5,3)	i	b	mismatch; skip (6,3) = 0	0
(4,3)	b	b	use (5,4) = 1; skip (5,3) = 0; sum 1+0	1
(3,3)	b	b	use (4,4) = 1; skip (4,3) = 1; sum 1+1	2
(7,2)	end	b	source exhausted before target	0
(6,2)	t	b	mismatch; skip (7,2) = 0	0
(5,2)	i	b	mismatch; skip (6,2) = 0	0
(4,2)	b	b	use (5,3) = 0; skip (5,2) = 0; sum 0+0	0
(3,2)	b	b	use (4,3) = 1; skip (4,2) = 0; sum 1+0	1
(2,2)	b	b	use (3,3) = 2; skip (3,2) = 1; sum 2+1	3
(7,1)	end	a	source exhausted before target	0
(6,1)	t	a	mismatch; skip (7,1) = 0	0
(5,1)	i	a	mismatch; skip (6,1) = 0	0
(4,1)	b	a	mismatch; skip (5,1) = 0	0
(3,1)	b	a	mismatch; skip (4,1) = 0	0
(2,1)	b	a	mismatch; skip (3,1) = 0	0
(1,1)	a	a	use (2,2) = 3; skip (2,1) = 0; sum 3+0	3
(7,0)	end	r	source exhausted before target	0
(6,0)	t	r	mismatch; skip (7,0) = 0	0
(5,0)	i	r	mismatch; skip (6,0) = 0	0
(4,0)	b	r	mismatch; skip (5,0) = 0	0
(3,0)	b	r	mismatch; skip (4,0) = 0	0
(2,0)	b	r	mismatch; skip (3,0) = 0	0
(1,0)	a	r	mismatch; skip (2,0) = 0	0
(0,0)	r	r	use (1,1) = 3; skip (1,0) = 0; sum 3+0	3

Complexity Analysis

Time Complexity

O(2^m)

Space Complexity

O(m)

Let m = s.length and n = t.length. Each level consumes one source position and creates at most two children, giving an O(2^m) upper bound; repeated-letter inputs near n = m/2 realize exponential work. Stack depth is O(m); no substrings or memo table are allocated. The trace lists every unique reached state in postorder; identical repeated uncached calls are merged for readability, but the code executes them each time. Counts are saturated at the signed 32-bit maximum, so arithmetic and storage per frame remain constant. This teaching baseline is unsuitable for branching maximum-size inputs. Python temporarily reserves m+100 frames and restores the previous limit in finally; Java and JavaScript still require runtime stack capacity for about m frames.

Code

Solution.java

1class Solution {2    public int numDistinct(String s, String t) {3        return dfs(s, t, 0, 0);4    }5
6    private int dfs(String s, String t, int i, int j) {7        // Exhausting both strings succeeds, so check the target first.8        if (j == t.length()) return 1;9        if (i == s.length()) return 0;10        int skip = dfs(s, t, i + 1, j);11        if (s.charAt(i) != t.charAt(j)) return skip;12        int use = dfs(s, t, i + 1, j + 1);13        // Nonnegative addition commutes with capping; widen before adding.14        return (int) Math.min(Integer.MAX_VALUE, (long) use + skip);15    }16}

Hints

Hint 1

Count source index choices rather than unique resulting strings; the b positions in Example 1 are interchangeable letters but different choices.

Hint 2

A matching source character can be skipped or used; a mismatching one can only be skipped. What does an exhausted target contribute?

Hint 3

Store counts for target prefix lengths. When adding one source character, which traversal order keeps the old shorter-prefix counts intact?

Hint 4

Cap intermediate counts at the guaranteed final maximum using nonnegative saturation; do not assume shorter-prefix counts fit merely because dp[n] does.

Edge Cases

A longer target than source cannot embed; s="a", t="aa" gives 0.
Identical strings have one embedding, even with repeated letters: all positions must be used.
A missing target letter gives 0 even when other target-prefix counts are huge: s="a" repeated 1000 times, t="a" repeated 500 times followed by "b".
English letters are case-sensitive: s="Aa", t="a" has one embedding.
Empty target/source states occur inside recursion although public inputs are nonempty; both exhausted must return 1.

Common Mistakes and Interview Tips

Ascending 1D updates reuse the current source index, incorrectly giving a positive count for s="a", t="aa".
Initializing dp[0] to 0 destroys every count; the empty target has exactly one embedding.
Counting only distinct spellings or using a set discards different source-position choices.
The final 32-bit guarantee does not protect intermediate prefix counts. A plain int can overflow; a wider fixed integer can still overflow for length 1000. Use proven saturation or arbitrary precision with an adjusted complexity analysis.
The recursive approach intentionally has no memoization and is infeasible for large branching inputs; explain the bottleneck before recommending the DP.
Python default recursion limits can fail on 1000 source characters. The published recursive snippet temporarily reserves room and restores the prior setting; use iterative DP for arbitrary caller depths.

Key Takeaway

Counting subsequence embeddings partitions choices into skip and match groups. Compressing prefix DP to one row requires backward updates so dependencies still refer to the previous source prefix; arithmetic must preserve counts even when irrelevant intermediate states are huge.