Distinct Subsequences II (LeetCode 940)
You get a string s of lowercase English letters. Deleting any number of its letters, possibly none, and keeping the rest in their original order gives a subsequence of s.
Count the different non-empty strings you can get this way. A string that several different choices of positions produce is counted once, not once per choice. The count can be very large, so return it modulo 109 + 7.
Worked Examples
s = "abc"7"a", "b", "c", "ab", "ac", "bc" and "abc".s = "aba"6"a", "b", "aa", "ab", "ba" and "aba". Picking only the first letter or only the last letter both give "a", which counts once.s = "aaa"3"a", "aa" and "aaa"; every other choice of positions repeats one of them.⚖️Formal Constraints & Bounds
1 <= s.length <= 2000sconsists of lowercase English letters.
Core Insight
Keep one running count per last letter, ends[c]. A new letter ch can finish every subsequence counted so far and can also stand alone, so ends[ch] becomes sum(ends) + 1 -- replacing, not adding to, the old ends[ch], because that old count is already included inside sum(ends).
Real-World Scenario & Production Applications
Counting how many distinct messages a noisy channel could have reduced to the received string, how many distinct search queries a typed prefix could abbreviate, or how many distinct DNA fragments a read could contain all reduce to counting distinct subsequences, where equal strings reached by different deletions must be counted once.
Step-by-Step Execution Trace Table
Example 1, s = "abc". Only the one letter ends[ch] touches on each row changes; every other entry of ends carries over unchanged:
| Step | ch | sum(ends) before | ends[ch] = sum(ends) + 1 | ends after (nonzero entries) |
|---|---|---|---|---|
| Start | ends = [0] * 26 | |||
| 1 | a | 0 | ends['a'] = 0 + 1 = 1 | a: 1 |
| 2 | b | 1 | ends['b'] = 1 + 1 = 2 | a: 1, b: 2 |
| 3 | c | 3 | ends['c'] = 3 + 1 = 4 | a: 1, b: 2, c: 4 |
| End | return sum(ends) | 7 |
| 1 | Give every possible last letter its own running count: `ends[c]` is how many distinct non-empty subsequences built from the characters read so far end in `c`. |
| 2 | A new character `ch` can finish `ch` alone, or finish any subsequence already counted by appending `ch` to it, so `ends[ch]` becomes `sum(ends) + 1`, and this replaces the old `ends[ch]` rather than adding to it. |
| 3 | The shape: one array of 26 counts, one loop over the characters of `s`, one replace per character, and the sum of the 26 counts at the end. |
| 4 | The trap: `ends[ch] += sum(ends) + 1` instead of `=`. The old `ends[ch]` already counted exactly the subsequences this same step rebuilds, so adding counts every one of them twice. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting every distinct subsequence of a string by listing them is exponential: a string of n letters has up to 2^n - 1 non-empty subsequences. Last-Character Counting DP reads s once instead, and keeps one running count per possible last letter: ends[c], how many distinct non-empty subsequences built from the letters read so far end in c. A new letter ch can finish every one of those counted subsequences by appending ch to it, and it can also stand alone as the one-letter subsequence "ch" -- both of those are new subsequences ending in ch, so ends[ch] becomes sum(ends) + 1.
🧺 The Analogy: One Basket per Last Ingredient, Refilled Each Time
Picture building every distinct trail mix you can make by adding ingredients one at a time, where two mixes are the same trail mix exactly when they contain the same ingredients in the same order. Keep one basket per ingredient, holding every distinct mix made so far that ends with that ingredient. When a new ingredient ch arrives, every mix in every basket can have ch added to its end to form a new, distinct mix -- plus ch on its own is a new one-ingredient mix -- so you empty the basket for ch and refill it with all of those at once. You never add to what was already in that basket, because every mix already in it is one of the mixes this same step just rebuilt by appending ch to a shorter mix.
🔑 Why It Works
The replace is what keeps every subsequence counted exactly once. The old ends[ch] already counted exactly the subsequences this same construction rebuilds: every subsequence that already ended in ch is reproduced, letter for letter, by appending ch to the subsequence left after removing that last ch -- so it is one of the sum(ends) subsequences ends[ch] = sum(ends) + 1 just built. Adding the new total on top of the old ends[ch], instead of replacing it, would count every one of those subsequences a second time.
Adding instead of replacing
ends[ch]:ends[ch] += sum(ends) + 1double-counts every subsequence that already ended inch, since that old count is already one of thesum(ends)terms this step rebuilds.s = "aaa"must return3("a","aa","aaa"), not more.Forgetting the
+ 1for the one-letter subsequence:ends[c] = sum(ends)never counts"c"alone.s = "abc"must return7, not0.Forgetting the final
% MODon the return line: eachends[c]is already reduced modulo109 + 7on every write, but summing 26 already-reduced values can still add up past the modulus;return sum(ends)alone can return a number at or above109 + 7, not the required remainder.Treating a repeated
'0'like'1'on LC 1987's transfer problem:ends0 = ends0 + ends1 + 1rebuilds the lone "0" subsequence once per'0'seen instead of once for the whole string;binary = "000"must return1, not3.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Count the different non-empty strings you can get" with no second string to match: the count is of every distinct subsequence of s itself. That is the signal for Last-Character Counting DP: one running count per possible last letter.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After each letter ch of s is read, ends[c] is the number of distinct non-empty subsequences built so far that end in c, and every subsequence that already ended in c is already included inside that same count, so the next letter rebuilds it rather than adding to it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
ends[c] = sum(ends)without the+ 1: the one-letter subsequence"c"itself is never counted the first timecappears (s = "abc"returns0instead of7).
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Last-Character Counting DP. I keep one running count per letter of the alphabet: ends of c is how many distinct non-empty subsequences I've built so far that end in c. For each new letter ch, every subsequence I've counted can have ch appended to it, and ch alone is also a new one-letter subsequence, so ends of ch becomes the sum of every count plus one. That replaces the old ends of ch, it doesn't add to it, because the old value is already inside that sum, and adding again would double-count every subsequence that already ended in ch. The answer is the sum of all 26 counts at the end. One pass over s, 26 counts to update each time, so
O(N)time andO(1)space.
Complexity & Mathematical Proof
O(N)
Look at the code: for ch in s runs N times, and its body computes sum(ends) over the 26 entries and writes one of them, both O(1) because 26 is a fixed constant, not N. Total: O(26 * N) = O(N).
O(1)
The code keeps one list, ends, of 26 counts, whatever the length of s: O(26) = O(1) extra space. The answer is one integer.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "count the different non-empty strings you can get this way", "a string that several choices of positions produce is counted once". A count of every distinct subsequence of one string, with no second string to match against: Last-Character Counting DP, one running count per last letter.
letters, so cheap steps. Listing every one of up to subsequences is exponential; the running counts are time and space. The answer is returned modulo .
In Java, C++, Go or Rust, sum(ends) + 1 must be reduced modulo on every write to ends[c], not only at the end: a fixed-width int silently overflows, including into a negative number, once the unreduced total passes the type's range. Python's integers never overflow, so the same mistake there only costs time on long strings.
Distinct Subsequences II (LeetCode 940)
You get a string s of lowercase English letters. Deleting any number of its letters, possibly none, and keeping the rest in their original order gives a subsequence of s.
Count the different non-empty strings you can get this way. A string that several different choices of positions produce is counted once, not once per choice. The count can be very large, so return it modulo 109 + 7.
Worked Examples
s = "abc"7"a", "b", "c", "ab", "ac", "bc" and "abc".s = "aba"6"a", "b", "aa", "ab", "ba" and "aba". Picking only the first letter or only the last letter both give "a", which counts once.s = "aaa"3"a", "aa" and "aaa"; every other choice of positions repeats one of them.⚖️Formal Constraints & Bounds
1 <= s.length <= 2000sconsists of lowercase English letters.
Core Insight
Keep one running count per last letter, ends[c]. A new letter ch can finish every subsequence counted so far and can also stand alone, so ends[ch] becomes sum(ends) + 1 -- replacing, not adding to, the old ends[ch], because that old count is already included inside sum(ends).
Real-World Scenario & Production Applications
Counting how many distinct messages a noisy channel could have reduced to the received string, how many distinct search queries a typed prefix could abbreviate, or how many distinct DNA fragments a read could contain all reduce to counting distinct subsequences, where equal strings reached by different deletions must be counted once.
Step-by-Step Execution Trace Table
Example 1, s = "abc". Only the one letter ends[ch] touches on each row changes; every other entry of ends carries over unchanged:
| Step | ch | sum(ends) before | ends[ch] = sum(ends) + 1 | ends after (nonzero entries) |
|---|---|---|---|---|
| Start | ends = [0] * 26 | |||
| 1 | a | 0 | ends['a'] = 0 + 1 = 1 | a: 1 |
| 2 | b | 1 | ends['b'] = 1 + 1 = 2 | a: 1, b: 2 |
| 3 | c | 3 | ends['c'] = 3 + 1 = 4 | a: 1, b: 2, c: 4 |
| End | return sum(ends) | 7 |
| 1 | Give every possible last letter its own running count: `ends[c]` is how many distinct non-empty subsequences built from the characters read so far end in `c`. |
| 2 | A new character `ch` can finish `ch` alone, or finish any subsequence already counted by appending `ch` to it, so `ends[ch]` becomes `sum(ends) + 1`, and this replaces the old `ends[ch]` rather than adding to it. |
| 3 | The shape: one array of 26 counts, one loop over the characters of `s`, one replace per character, and the sum of the 26 counts at the end. |
| 4 | The trap: `ends[ch] += sum(ends) + 1` instead of `=`. The old `ends[ch]` already counted exactly the subsequences this same step rebuilds, so adding counts every one of them twice. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting every distinct subsequence of a string by listing them is exponential: a string of n letters has up to 2^n - 1 non-empty subsequences. Last-Character Counting DP reads s once instead, and keeps one running count per possible last letter: ends[c], how many distinct non-empty subsequences built from the letters read so far end in c. A new letter ch can finish every one of those counted subsequences by appending ch to it, and it can also stand alone as the one-letter subsequence "ch" -- both of those are new subsequences ending in ch, so ends[ch] becomes sum(ends) + 1.
🧺 The Analogy: One Basket per Last Ingredient, Refilled Each Time
Picture building every distinct trail mix you can make by adding ingredients one at a time, where two mixes are the same trail mix exactly when they contain the same ingredients in the same order. Keep one basket per ingredient, holding every distinct mix made so far that ends with that ingredient. When a new ingredient ch arrives, every mix in every basket can have ch added to its end to form a new, distinct mix -- plus ch on its own is a new one-ingredient mix -- so you empty the basket for ch and refill it with all of those at once. You never add to what was already in that basket, because every mix already in it is one of the mixes this same step just rebuilt by appending ch to a shorter mix.
🔑 Why It Works
The replace is what keeps every subsequence counted exactly once. The old ends[ch] already counted exactly the subsequences this same construction rebuilds: every subsequence that already ended in ch is reproduced, letter for letter, by appending ch to the subsequence left after removing that last ch -- so it is one of the sum(ends) subsequences ends[ch] = sum(ends) + 1 just built. Adding the new total on top of the old ends[ch], instead of replacing it, would count every one of those subsequences a second time.
Adding instead of replacing
ends[ch]:ends[ch] += sum(ends) + 1double-counts every subsequence that already ended inch, since that old count is already one of thesum(ends)terms this step rebuilds.s = "aaa"must return3("a","aa","aaa"), not more.Forgetting the
+ 1for the one-letter subsequence:ends[c] = sum(ends)never counts"c"alone.s = "abc"must return7, not0.Forgetting the final
% MODon the return line: eachends[c]is already reduced modulo109 + 7on every write, but summing 26 already-reduced values can still add up past the modulus;return sum(ends)alone can return a number at or above109 + 7, not the required remainder.Treating a repeated
'0'like'1'on LC 1987's transfer problem:ends0 = ends0 + ends1 + 1rebuilds the lone "0" subsequence once per'0'seen instead of once for the whole string;binary = "000"must return1, not3.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Count the different non-empty strings you can get" with no second string to match: the count is of every distinct subsequence of s itself. That is the signal for Last-Character Counting DP: one running count per possible last letter.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After each letter ch of s is read, ends[c] is the number of distinct non-empty subsequences built so far that end in c, and every subsequence that already ended in c is already included inside that same count, so the next letter rebuilds it rather than adding to it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
ends[c] = sum(ends)without the+ 1: the one-letter subsequence"c"itself is never counted the first timecappears (s = "abc"returns0instead of7).
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Last-Character Counting DP. I keep one running count per letter of the alphabet: ends of c is how many distinct non-empty subsequences I've built so far that end in c. For each new letter ch, every subsequence I've counted can have ch appended to it, and ch alone is also a new one-letter subsequence, so ends of ch becomes the sum of every count plus one. That replaces the old ends of ch, it doesn't add to it, because the old value is already inside that sum, and adding again would double-count every subsequence that already ended in ch. The answer is the sum of all 26 counts at the end. One pass over s, 26 counts to update each time, so
O(N)time andO(1)space.
Complexity & Mathematical Proof
O(N)
Look at the code: for ch in s runs N times, and its body computes sum(ends) over the 26 entries and writes one of them, both O(1) because 26 is a fixed constant, not N. Total: O(26 * N) = O(N).
O(1)
The code keeps one list, ends, of 26 counts, whatever the length of s: O(26) = O(1) extra space. The answer is one integer.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "count the different non-empty strings you can get this way", "a string that several choices of positions produce is counted once". A count of every distinct subsequence of one string, with no second string to match against: Last-Character Counting DP, one running count per last letter.
letters, so cheap steps. Listing every one of up to subsequences is exponential; the running counts are time and space. The answer is returned modulo .
In Java, C++, Go or Rust, sum(ends) + 1 must be reduced modulo on every write to ends[c], not only at the end: a fixed-width int silently overflows, including into a negative number, once the unreduced total passes the type's range. Python's integers never overflow, so the same mistake there only costs time on long strings.