Distinct Subsequences (LeetCode 115)
You get two strings, s and t. Choose some positions of s and read their letters from left to right, skipping the others: the result is a subsequence of s.
Count how many different choices of positions spell exactly t. Two choices are different when at least one position differs, even though both spell t. Upper-case and lower-case letters are different letters. The answer is never larger than 2^31 - 1.
Worked Examples
s = "rabbbit", t = "rabbit"3s has three bs in a row and t needs two of them; every other letter of t has exactly one place it can come from. Two of three bs can be chosen in 3 ways.s = "babgbag", t = "bag"5b, a, g can come from positions (0, 1, 3), (0, 1, 6), (0, 5, 6), (2, 5, 6) or (4, 5, 6): 5 choices.⚖️Formal Constraints & Bounds
1 <= s.length, t.length <= 1000sandtconsist of English letters.
Core Insight
A character of s is either skipped or used as the next letter of some prefix of t, so one count per prefix, ways[j], is all the history you need: a matching character adds the count one letter shorter, ways[j - 1], read before that same character changed it.
Real-World Scenario & Production Applications
Scoring how strongly a short pattern occurs inside a long sequence, for example a motif in a DNA read or a keystroke pattern in an event log, often means counting every way the pattern can be picked out in order, gaps allowed. The count comes from the same running tallies, one per prefix of the pattern, updated once per symbol.
Step-by-Step Execution Trace Table
Example 1, s = "rabbbit", t = "rabbit" (n = 6). Each row reads one character ch; only the j with t[j - 1] == ch change, in the order the backwards loop visits them:
| Step | ch | Updates (j from 6 down to 1) | ways after the row |
|---|---|---|---|
| Start | ways = [1] + [0] * 6 | [1, 0, 0, 0, 0, 0, 0] | |
| 1 | r | ways[1] += ways[0]: 0 + 1 = 1 | [1, 1, 0, 0, 0, 0, 0] |
| 2 | a | ways[2] += ways[1]: 0 + 1 = 1 | [1, 1, 1, 0, 0, 0, 0] |
| 3 | b | ways[4] += ways[3]: 0 + 0 = 0, then ways[3] += ways[2]: 0 + 1 = 1 | [1, 1, 1, 1, 0, 0, 0] |
| 4 | b | ways[4] += ways[3]: 0 + 1 = 1, then ways[3] += ways[2]: 1 + 1 = 2 | [1, 1, 1, 2, 1, 0, 0] |
| 5 | b | ways[4] += ways[3]: 1 + 2 = 3, then ways[3] += ways[2]: 2 + 1 = 3 | [1, 1, 1, 3, 3, 0, 0] |
| 6 | i | ways[5] += ways[4]: 0 + 3 = 3 | [1, 1, 1, 3, 3, 3, 0] |
| 7 | t | ways[6] += ways[5]: 0 + 3 = 3 | [1, 1, 1, 3, 3, 3, 3] |
| End | return ways[6] | 3 |
At step 3, ways[4] reads ways[3] = 0 before this b raises it: no "rab" ends before the first b. Running j upwards would raise ways[3] to 1 first and then count "rabb" with one b used twice; carried on, that returns 6.
| 1 | Read `s` once; `ways[j]` counts the ways to spell `t[:j]` from the characters read so far, and `ways[0] = 1` because the empty prefix is spelled by picking nothing. |
| 2 | A character `ch` is either skipped (every count stays) or used as `t[j - 1]` where the letters match: `ways[j] += ways[j - 1]`. |
| 3 | The shape: one list of counts for the prefixes of `t`, an outer loop over the characters of `s`, an inner loop over the prefix lengths `j`, one update where the letters match, and the count for the whole of `t` at the end. |
| 4 | The trap: `j` runs from `n` down to `1`. Going up, `ways[j - 1]` already includes this `ch`, so one letter fills two places of `t` (`"rabbbit"`, `"rabbit"` gives 6 instead of 3). |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting how many ways t sits inside s as a subsequence looks like a search over every set of positions, and there are exponentially many. Subsequence Counting DP reads s once instead. After each character it keeps one number per prefix of t: ways[j], the ways to spell t[:j] with the characters read so far. A new character ch either is skipped, which leaves every count as it was, or finishes a prefix whose last letter is ch, which adds the ways to spell the prefix one letter shorter.
🧵 The Analogy: Threading Beads in Order
Think of t as a pattern of beads to thread, and s as a box of beads that come out one at a time. For every partly threaded pattern you keep a tally of how many different ways you got there. When a bead comes out, every tally whose next bead has that colour can grow by one bead, and every tally can also ignore it. You never need to remember which beads were used, only the tallies.
🔑 Why It Works
This is the two-row recurrence ways[i][j] = ways[i - 1][j] + ways[i - 1][j - 1] (the second term only when s[i - 1] == t[j - 1]) folded into one row. The right-hand side must still be the previous row, so j runs from n down to 1: ways[j - 1] is then read before this ch changes it. Going up, the same letter of s would fill t[j - 2] and t[j - 1] at once.
Running
jforwards:for j in range(n, 0, -1)runs fromndown. Going up,ways[j - 1]already includes the currentch, so one letter ofsfills two places oft:"rabbbit","rabbit"returns 6 instead of 3.Replacing instead of adding:
ways[j] += ways[j - 1], not=. The ways that skipchare still valid, so"ccc","c"needs 3, not 1.No seed for the empty prefix: start with
ways = [1] + [0] * n. The empty prefixt[:0]is spelled once, by picking nothing; withways[0] = 0no match can ever start.Reading the wrong letter of
t:ways[j]is the count for the prefixt[:j], whose last letter ist[j - 1]. Comparingt[j] == chmatches the next letter instead, and atj = nit runs past the end oft.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Choose some positions of s and read their letters from left to right" plus "count how many different choices of positions spell exactly t": the order is fixed and every character of s is either picked or skipped, so the question is a count over in-order picks, not one best alignment. That is the signal for Subsequence Counting DP: one running count per prefix of t, updated once per character of s.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
With ways[j] as in the card's invariant, each character ch of s updates it once. For j from n down to 1: if t[j - 1] == ch, then ways[j] += ways[j - 1] (the old ways[j] skip ch, the ways[j - 1] ways finish t[:j] with it). The answer is ways[n].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Subsequence Counting DP. Every character of s is either skipped or used as the next letter of t, so I keep one count per prefix of t: ways of j is the number of ways to spell the first j letters with what I've read so far. ways of zero is one, the empty prefix. For each character of s, I walk j from n down to one, and where t of j minus one equals that character, I add ways of j minus one into ways of j. The old value counts the ways that skip the character, and the added value counts the ways that finish with it. Walking j backwards is the trap it avoids: going up, ways of j minus one would already include this same character, and one letter of s would fill two places of t. The answer is ways of n. That's O(M times N) time and
O(N)space.
Complexity & Mathematical Proof
O(M * N)
Look at the code: for ch in s runs M times, and for each character for j in range(n, 0, -1) runs N times. The body does one comparison, t[j - 1] == ch, and at most one addition, so it is O(1). Building ways takes N + 1 steps once. Total: O(M * N).
O(N)
The code keeps one list, ways, of N + 1 counts, plus n, ch and j. It never stores a full M x N table: each character's row overwrites the previous one in place, which is safe because j runs backwards. The answer is one integer.
Derivation Progression
O(N)
ways = [1] + [0] * n builds N + 1 counts once.
M iterations
for ch in s reads every character of s once.
N iterations per character
for j in range(n, 0, -1) visits every prefix length from N down to 1.
O(1)
One comparison t[j - 1] == ch and at most one addition ways[j] += ways[j - 1].
O(M * N)
M characters times N prefixes, constant work each; the answer is read from ways[n].
Variable Definitions
Length of s, the string the letters are picked from
Length of t, the string to spell (n = len(t) in the code)
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N): the ways list of N + 1 counts
O(1): one integer
Boundary Best / Worst Cases
: the inner loop runs over every j even when no letter matches
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "choose some positions of s and read their letters from left to right", "count how many different choices of positions spell exactly t". A count over in-order picks where every character is used or skipped: Subsequence Counting DP, one running count per prefix of t.
, so cheap steps. Trying every set of positions is , and the memo-free skip-or-use recursion is up to ; the running counts are time and space. The answer fits a 32-bit integer, but counts for short prefixes of t can be astronomically larger.
In C++ or Rust, a count that never reaches the answer can overflow even though the answer fits: use unsigned or wrapping additions there, since every count that does feed ways[n] is never larger than the answer. Python's integers need no change, and the silent wrap-around of Java, Go and C# integers is harmless for the same reason.
Distinct Subsequences (LeetCode 115)
You get two strings, s and t. Choose some positions of s and read their letters from left to right, skipping the others: the result is a subsequence of s.
Count how many different choices of positions spell exactly t. Two choices are different when at least one position differs, even though both spell t. Upper-case and lower-case letters are different letters. The answer is never larger than 2^31 - 1.
Worked Examples
s = "rabbbit", t = "rabbit"3s has three bs in a row and t needs two of them; every other letter of t has exactly one place it can come from. Two of three bs can be chosen in 3 ways.s = "babgbag", t = "bag"5b, a, g can come from positions (0, 1, 3), (0, 1, 6), (0, 5, 6), (2, 5, 6) or (4, 5, 6): 5 choices.⚖️Formal Constraints & Bounds
1 <= s.length, t.length <= 1000sandtconsist of English letters.
Core Insight
A character of s is either skipped or used as the next letter of some prefix of t, so one count per prefix, ways[j], is all the history you need: a matching character adds the count one letter shorter, ways[j - 1], read before that same character changed it.
Real-World Scenario & Production Applications
Scoring how strongly a short pattern occurs inside a long sequence, for example a motif in a DNA read or a keystroke pattern in an event log, often means counting every way the pattern can be picked out in order, gaps allowed. The count comes from the same running tallies, one per prefix of the pattern, updated once per symbol.
Step-by-Step Execution Trace Table
Example 1, s = "rabbbit", t = "rabbit" (n = 6). Each row reads one character ch; only the j with t[j - 1] == ch change, in the order the backwards loop visits them:
| Step | ch | Updates (j from 6 down to 1) | ways after the row |
|---|---|---|---|
| Start | ways = [1] + [0] * 6 | [1, 0, 0, 0, 0, 0, 0] | |
| 1 | r | ways[1] += ways[0]: 0 + 1 = 1 | [1, 1, 0, 0, 0, 0, 0] |
| 2 | a | ways[2] += ways[1]: 0 + 1 = 1 | [1, 1, 1, 0, 0, 0, 0] |
| 3 | b | ways[4] += ways[3]: 0 + 0 = 0, then ways[3] += ways[2]: 0 + 1 = 1 | [1, 1, 1, 1, 0, 0, 0] |
| 4 | b | ways[4] += ways[3]: 0 + 1 = 1, then ways[3] += ways[2]: 1 + 1 = 2 | [1, 1, 1, 2, 1, 0, 0] |
| 5 | b | ways[4] += ways[3]: 1 + 2 = 3, then ways[3] += ways[2]: 2 + 1 = 3 | [1, 1, 1, 3, 3, 0, 0] |
| 6 | i | ways[5] += ways[4]: 0 + 3 = 3 | [1, 1, 1, 3, 3, 3, 0] |
| 7 | t | ways[6] += ways[5]: 0 + 3 = 3 | [1, 1, 1, 3, 3, 3, 3] |
| End | return ways[6] | 3 |
At step 3, ways[4] reads ways[3] = 0 before this b raises it: no "rab" ends before the first b. Running j upwards would raise ways[3] to 1 first and then count "rabb" with one b used twice; carried on, that returns 6.
| 1 | Read `s` once; `ways[j]` counts the ways to spell `t[:j]` from the characters read so far, and `ways[0] = 1` because the empty prefix is spelled by picking nothing. |
| 2 | A character `ch` is either skipped (every count stays) or used as `t[j - 1]` where the letters match: `ways[j] += ways[j - 1]`. |
| 3 | The shape: one list of counts for the prefixes of `t`, an outer loop over the characters of `s`, an inner loop over the prefix lengths `j`, one update where the letters match, and the count for the whole of `t` at the end. |
| 4 | The trap: `j` runs from `n` down to `1`. Going up, `ways[j - 1]` already includes this `ch`, so one letter fills two places of `t` (`"rabbbit"`, `"rabbit"` gives 6 instead of 3). |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting how many ways t sits inside s as a subsequence looks like a search over every set of positions, and there are exponentially many. Subsequence Counting DP reads s once instead. After each character it keeps one number per prefix of t: ways[j], the ways to spell t[:j] with the characters read so far. A new character ch either is skipped, which leaves every count as it was, or finishes a prefix whose last letter is ch, which adds the ways to spell the prefix one letter shorter.
🧵 The Analogy: Threading Beads in Order
Think of t as a pattern of beads to thread, and s as a box of beads that come out one at a time. For every partly threaded pattern you keep a tally of how many different ways you got there. When a bead comes out, every tally whose next bead has that colour can grow by one bead, and every tally can also ignore it. You never need to remember which beads were used, only the tallies.
🔑 Why It Works
This is the two-row recurrence ways[i][j] = ways[i - 1][j] + ways[i - 1][j - 1] (the second term only when s[i - 1] == t[j - 1]) folded into one row. The right-hand side must still be the previous row, so j runs from n down to 1: ways[j - 1] is then read before this ch changes it. Going up, the same letter of s would fill t[j - 2] and t[j - 1] at once.
Running
jforwards:for j in range(n, 0, -1)runs fromndown. Going up,ways[j - 1]already includes the currentch, so one letter ofsfills two places oft:"rabbbit","rabbit"returns 6 instead of 3.Replacing instead of adding:
ways[j] += ways[j - 1], not=. The ways that skipchare still valid, so"ccc","c"needs 3, not 1.No seed for the empty prefix: start with
ways = [1] + [0] * n. The empty prefixt[:0]is spelled once, by picking nothing; withways[0] = 0no match can ever start.Reading the wrong letter of
t:ways[j]is the count for the prefixt[:j], whose last letter ist[j - 1]. Comparingt[j] == chmatches the next letter instead, and atj = nit runs past the end oft.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Choose some positions of s and read their letters from left to right" plus "count how many different choices of positions spell exactly t": the order is fixed and every character of s is either picked or skipped, so the question is a count over in-order picks, not one best alignment. That is the signal for Subsequence Counting DP: one running count per prefix of t, updated once per character of s.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
With ways[j] as in the card's invariant, each character ch of s updates it once. For j from n down to 1: if t[j - 1] == ch, then ways[j] += ways[j - 1] (the old ways[j] skip ch, the ways[j - 1] ways finish t[:j] with it). The answer is ways[n].
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Subsequence Counting DP. Every character of s is either skipped or used as the next letter of t, so I keep one count per prefix of t: ways of j is the number of ways to spell the first j letters with what I've read so far. ways of zero is one, the empty prefix. For each character of s, I walk j from n down to one, and where t of j minus one equals that character, I add ways of j minus one into ways of j. The old value counts the ways that skip the character, and the added value counts the ways that finish with it. Walking j backwards is the trap it avoids: going up, ways of j minus one would already include this same character, and one letter of s would fill two places of t. The answer is ways of n. That's O(M times N) time and
O(N)space.
Complexity & Mathematical Proof
O(M * N)
Look at the code: for ch in s runs M times, and for each character for j in range(n, 0, -1) runs N times. The body does one comparison, t[j - 1] == ch, and at most one addition, so it is O(1). Building ways takes N + 1 steps once. Total: O(M * N).
O(N)
The code keeps one list, ways, of N + 1 counts, plus n, ch and j. It never stores a full M x N table: each character's row overwrites the previous one in place, which is safe because j runs backwards. The answer is one integer.
Derivation Progression
O(N)
ways = [1] + [0] * n builds N + 1 counts once.
M iterations
for ch in s reads every character of s once.
N iterations per character
for j in range(n, 0, -1) visits every prefix length from N down to 1.
O(1)
One comparison t[j - 1] == ch and at most one addition ways[j] += ways[j - 1].
O(M * N)
M characters times N prefixes, constant work each; the answer is read from ways[n].
Variable Definitions
Length of s, the string the letters are picked from
Length of t, the string to spell (n = len(t) in the code)
Memory Architecture & Bounds
O(1): iterative, no recursion
O(N): the ways list of N + 1 counts
O(1): one integer
Boundary Best / Worst Cases
: the inner loop runs over every j even when no letter matches
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "choose some positions of s and read their letters from left to right", "count how many different choices of positions spell exactly t". A count over in-order picks where every character is used or skipped: Subsequence Counting DP, one running count per prefix of t.
, so cheap steps. Trying every set of positions is , and the memo-free skip-or-use recursion is up to ; the running counts are time and space. The answer fits a 32-bit integer, but counts for short prefixes of t can be astronomically larger.
In C++ or Rust, a count that never reaches the answer can overflow even though the answer fits: use unsigned or wrapping additions there, since every count that does feed ways[n] is never larger than the answer. Python's integers need no change, and the silent wrap-around of Java, Go and C# integers is harmless for the same reason.