Builds on State Machine DP, which you haven’t finished yet.
Last-Character Counting DP (Distinct Subsequences II)
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.
"a", "b", "c", "ab", "ac", "bc" and "abc".Last-Char Counting DP
s -> ends[26], one count per last letter -> replace on each new letter| 1 | def distinctSubseqII(s: str) -> int: |
| 2 | """Counts the distinct non-empty subsequences of s, one running count per last letter. |
| 3 | Time: O(26 * N) = O(N) | Space: O(26) = O(1) |
| 4 | """ |
| 5 | MOD = 10**9 + 7 |
| 6 | ends = [0] * 26 # ends[c]: distinct non-empty subsequences built so far that end with letter c |
| 7 | for ch in s: |
| 8 | ends[ord(ch) - ord("a")] = (sum(ends) + 1) % MOD # Replace: the old ones ending in ch are rebuilt here |
| 9 | return sum(ends) % MOD |
s is read, ends[c] is the number of different non-empty subsequences built so far that end in letter c, and every subsequence that already ended in c is already included inside that same count.Keep one running count per last letter: ends[c] is how many different non-empty subsequences built so far end in c. A new letter ch can finish every one of those subsequences by appending ch to it, and it can also stand alone as the one-letter subsequence "ch", so ends[ch] = sum(ends) + 1 replaces the old ends[ch] instead of adding to it. The replacement is correct because 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, and keeping the old count too would count it a second time. The trap is writing ends[ch] += sum(ends) + 1: adding instead of replacing double-counts every repeat of a letter, so s = "aaa" returns more than the 3 distinct subsequences "a", "aa", "aaa".
See it run
Distinct Subsequences II with ends, step by step
letters read 0 of 3sum(ends) 0
Each column is one letter c. Each cell is ends[c], the number of distinct subsequences that end in c.
chthe letter being readsummeda count that is added into sum(ends)replacedthe count of ch, which gets the new value
Start: ends is all zeros. No subsequence has been built from s = "aba".
Gotcha 1 of 3
- The trap
Gotcha 1: Adding instead of replacing
ends[ch](the card's trap)Mistakeends[ord(ch) - ord("a")] = (sum(ends) + 1 + ends[ord(ch) - ord("a")]) % MODFixends[ord(ch) - ord("a")] = (sum(ends) + 1) % MODWhat happens: The old
ends[ch]is already one of thesum(ends)subsequences this step rebuilds: every subsequence that already ended inchis reproduced by appendingchto the subsequence left after removing its lastch. Adding the old value on top counts each of those a second time, so repeats of a letter inflate the answer.Example: s = "aaa"Mistake: returns 7Fix: returns 3
- At each step you are in one of a few fixed modes (holding a stock or not) with simple rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): here there is no small fixed set of modes, only one running count per last letter, and a new letter replaces every one of those counts that it can finish, not just one mode's value. See State Machine DP
- You are counting how many ways one target string
tcan be picked out of a second strings, as in Distinct Subsequences (LC 115): here there is no second string to match, so the count is of every distinct subsequence ofsitself, keyed by last letter instead of by position int. See Distinct Subsequences
Deep Dive
What each count means
A subsequence keeps some letters of s in their original order. It may skip letters. The problem asks for the number of different non-empty subsequences, so two choices of positions that spell the same text count once.
State Machine DP keeps one best value per mode. This card keeps one count per mode, and the mode is the last letter of the subsequence. ends[c] is the number of different non-empty subsequences built so far that end in the letter c. There are 26 modes.
Example: after reading "aba", ends for a is 4 and for b is 2. The six subsequences are a, aa, ba, aba (end in a, and there are 4 of them) and b, ab (end in b).
Why ends[ch] = sum(ends) + 1 is correct
When the letter ch is read, every subsequence built so far can be extended with ch. That gives sum(ends) new subsequences that end in ch. The letter ch alone is one more, so the total is sum(ends) + 1.
These new subsequences are all different from each other, because they come from different earlier subsequences or from the empty start. They also include every subsequence that already ended in ch. Such a subsequence is the earlier one with its last ch removed, plus ch.
So ends[ch] already counted a subset of the new group. The new value is the full group, and it replaces the old one. Adding to the old value would count that subset twice.
Example: reading "aaa" gives ends for a equal to 1, then 2, then 3. Adding instead gives 1, 3, 7, and the answer 7 is wrong.
Why the other letters stay unchanged
Reading ch does not remove any subsequence that was built before. A subsequence that ends in another letter d is still a valid subsequence of the longer string. So ends[d] keeps its value.
Only the subsequences that end in ch can be new. All of them are created in the single assignment to ends[ch]. The loop invariant holds again after each letter.
The answer is sum(ends) % MOD. Every different non-empty subsequence has exactly one last letter, so it is counted in exactly one entry of ends.
The cost and the modulus
The card's complexity line is O(26 * N) time and O(26) space. For each of the N letters, sum(ends) adds 26 numbers. 26 is a constant, so this is O(N) time and O(1) space.
The number of subsequences can reach 2^N - 1, so the problem asks for the result modulo 10^9 + 7. Python integers do not overflow, but the values would become very large. The code reduces each written value with % MOD.
Each ends[c] is below MOD, but the sum of 26 of them can be larger than MOD. So the return line still needs % MOD. Example: distinctSubseqII("ab" * 100) returns 407981058.
60-Second Pitch
"I need the number of different non-empty subsequences. I keep one count per last letter, ends[c]. When I read a letter ch, I can extend every subsequence built so far, and I can also start a new one with ch alone. So the new group ending in ch has sum(ends) + 1 members. That group already contains everything that ended in ch before, so I replace ends[ch] and I do not add to it. For "aaa" the counts are 1, 2, 3. I take everything modulo 10^9 + 7. The time is O(26 * N), which is O(N), and the space is O(26), which is O(1)."
Common Questions
- Why do we replace
ends[ch]and not add to it? The new value
sum(ends) + 1already includes every subsequence that ended inchbefore. Each of those is a shorter subsequence plusch. Adding the old value counts them twice. For"aaa"the right answer is 3 and the adding version gives 7.- How would you count distinct subsequences with an
O(N)table instead of 26 counts? Let
dp[i]be the number of distinct subsequences of the firstiletters. Usedp[i] = 2 * dp[i - 1], and subtractdp[last - 1]when the letter appeared before at positionlast. This subtracts the subsequences that would be created twice. The 26 counts give the same result.- What changes if the alphabet is not limited to 26 letters?
Use a dictionary from letter to count, and keep a running total. Update the total with
total = total - old + new. Then each letter costsO(1), and the time isO(N). The space is the number of different letters.- How is this different from Distinct Subsequences (LC 115)?
Distinct Subsequences (LC 115) counts how many ways a fixed string
tappears insides, so the state is a position int. Here no target is given. We count every different subsequence of one string, so the state is the last letter.- What is the time and space complexity?
O(26 * N), which is
O(N), time and O(26), which isO(1), space. Each letter does one sum over 26 numbers and one write. The result is reduced modulo 10^9 + 7.
SWE Reasoning
Spot it
- You count something over one string, and no second string is given to match against.
- The word "distinct" or "different" appears. Two choices of positions that give the same text must count once.
- The brute force lists subsets of positions and puts the texts in a set. That is 2^N subsets, which is too slow for 2000 letters.
- A new letter extends what exists, and the only fact you need about an old subsequence is its last letter.
- The alphabet is small and fixed (26 letters), so one count per letter is cheap.
The invariant, step by step
- Before the loop,
ends = [0] * 26. No subsequence has been built. - A letter
chis read. Its index isord(ch) - ord("a"). - Every subsequence built so far can be extended with
ch. There aresum(ends)of them. The letterchalone gives one more, so the new group hassum(ends) + 1subsequences. - This group contains every subsequence that already ended in
ch, because each one is a shorter subsequence plusch. So the oldends[ch]is replaced, not added to. - The code writes
ends[ch] = (sum(ends) + 1) % MOD. All other entries stay unchanged. - After the last letter, each different non-empty subsequence is counted once, in the entry of its last letter. So
sum(ends) % MODis the answer.
Traps
- Adding instead of replacing, on a string that is not one repeated letter. For
"aba", the secondamust giveendsforaequal to 4. Adding the old value 1 gives 5 there, and the final answer is 7 instead of 6. - Counting the empty string. The problem asks for non-empty subsequences. If you count the empty string as one more subsequence and do not remove it at the end,
"a"returns 2 instead of 1. - Using a set of strings. Storing every subsequence takes exponential memory. For a string of 2000 letters this cannot finish. Count by last letter instead.
Practice
Builds on State Machine DP, which you haven’t finished yet.
Last-Character Counting DP (Distinct Subsequences II)
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.
"a", "b", "c", "ab", "ac", "bc" and "abc".Last-Char Counting DP
s -> ends[26], one count per last letter -> replace on each new letter| 1 | def distinctSubseqII(s: str) -> int: |
| 2 | """Counts the distinct non-empty subsequences of s, one running count per last letter. |
| 3 | Time: O(26 * N) = O(N) | Space: O(26) = O(1) |
| 4 | """ |
| 5 | MOD = 10**9 + 7 |
| 6 | ends = [0] * 26 # ends[c]: distinct non-empty subsequences built so far that end with letter c |
| 7 | for ch in s: |
| 8 | ends[ord(ch) - ord("a")] = (sum(ends) + 1) % MOD # Replace: the old ones ending in ch are rebuilt here |
| 9 | return sum(ends) % MOD |
s is read, ends[c] is the number of different non-empty subsequences built so far that end in letter c, and every subsequence that already ended in c is already included inside that same count.Keep one running count per last letter: ends[c] is how many different non-empty subsequences built so far end in c. A new letter ch can finish every one of those subsequences by appending ch to it, and it can also stand alone as the one-letter subsequence "ch", so ends[ch] = sum(ends) + 1 replaces the old ends[ch] instead of adding to it. The replacement is correct because 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, and keeping the old count too would count it a second time. The trap is writing ends[ch] += sum(ends) + 1: adding instead of replacing double-counts every repeat of a letter, so s = "aaa" returns more than the 3 distinct subsequences "a", "aa", "aaa".
See it run
Distinct Subsequences II with ends, step by step
letters read 0 of 3sum(ends) 0
Each column is one letter c. Each cell is ends[c], the number of distinct subsequences that end in c.
chthe letter being readsummeda count that is added into sum(ends)replacedthe count of ch, which gets the new value
Start: ends is all zeros. No subsequence has been built from s = "aba".
Gotcha 1 of 3
- The trap
Gotcha 1: Adding instead of replacing
ends[ch](the card's trap)Mistakeends[ord(ch) - ord("a")] = (sum(ends) + 1 + ends[ord(ch) - ord("a")]) % MODFixends[ord(ch) - ord("a")] = (sum(ends) + 1) % MODWhat happens: The old
ends[ch]is already one of thesum(ends)subsequences this step rebuilds: every subsequence that already ended inchis reproduced by appendingchto the subsequence left after removing its lastch. Adding the old value on top counts each of those a second time, so repeats of a letter inflate the answer.Example: s = "aaa"Mistake: returns 7Fix: returns 3
- At each step you are in one of a few fixed modes (holding a stock or not) with simple rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): here there is no small fixed set of modes, only one running count per last letter, and a new letter replaces every one of those counts that it can finish, not just one mode's value. See State Machine DP
- You are counting how many ways one target string
tcan be picked out of a second strings, as in Distinct Subsequences (LC 115): here there is no second string to match, so the count is of every distinct subsequence ofsitself, keyed by last letter instead of by position int. See Distinct Subsequences
Deep Dive
What each count means
A subsequence keeps some letters of s in their original order. It may skip letters. The problem asks for the number of different non-empty subsequences, so two choices of positions that spell the same text count once.
State Machine DP keeps one best value per mode. This card keeps one count per mode, and the mode is the last letter of the subsequence. ends[c] is the number of different non-empty subsequences built so far that end in the letter c. There are 26 modes.
Example: after reading "aba", ends for a is 4 and for b is 2. The six subsequences are a, aa, ba, aba (end in a, and there are 4 of them) and b, ab (end in b).
Why ends[ch] = sum(ends) + 1 is correct
When the letter ch is read, every subsequence built so far can be extended with ch. That gives sum(ends) new subsequences that end in ch. The letter ch alone is one more, so the total is sum(ends) + 1.
These new subsequences are all different from each other, because they come from different earlier subsequences or from the empty start. They also include every subsequence that already ended in ch. Such a subsequence is the earlier one with its last ch removed, plus ch.
So ends[ch] already counted a subset of the new group. The new value is the full group, and it replaces the old one. Adding to the old value would count that subset twice.
Example: reading "aaa" gives ends for a equal to 1, then 2, then 3. Adding instead gives 1, 3, 7, and the answer 7 is wrong.
Why the other letters stay unchanged
Reading ch does not remove any subsequence that was built before. A subsequence that ends in another letter d is still a valid subsequence of the longer string. So ends[d] keeps its value.
Only the subsequences that end in ch can be new. All of them are created in the single assignment to ends[ch]. The loop invariant holds again after each letter.
The answer is sum(ends) % MOD. Every different non-empty subsequence has exactly one last letter, so it is counted in exactly one entry of ends.
The cost and the modulus
The card's complexity line is O(26 * N) time and O(26) space. For each of the N letters, sum(ends) adds 26 numbers. 26 is a constant, so this is O(N) time and O(1) space.
The number of subsequences can reach 2^N - 1, so the problem asks for the result modulo 10^9 + 7. Python integers do not overflow, but the values would become very large. The code reduces each written value with % MOD.
Each ends[c] is below MOD, but the sum of 26 of them can be larger than MOD. So the return line still needs % MOD. Example: distinctSubseqII("ab" * 100) returns 407981058.
60-Second Pitch
"I need the number of different non-empty subsequences. I keep one count per last letter, ends[c]. When I read a letter ch, I can extend every subsequence built so far, and I can also start a new one with ch alone. So the new group ending in ch has sum(ends) + 1 members. That group already contains everything that ended in ch before, so I replace ends[ch] and I do not add to it. For "aaa" the counts are 1, 2, 3. I take everything modulo 10^9 + 7. The time is O(26 * N), which is O(N), and the space is O(26), which is O(1)."
Common Questions
- Why do we replace
ends[ch]and not add to it? The new value
sum(ends) + 1already includes every subsequence that ended inchbefore. Each of those is a shorter subsequence plusch. Adding the old value counts them twice. For"aaa"the right answer is 3 and the adding version gives 7.- How would you count distinct subsequences with an
O(N)table instead of 26 counts? Let
dp[i]be the number of distinct subsequences of the firstiletters. Usedp[i] = 2 * dp[i - 1], and subtractdp[last - 1]when the letter appeared before at positionlast. This subtracts the subsequences that would be created twice. The 26 counts give the same result.- What changes if the alphabet is not limited to 26 letters?
Use a dictionary from letter to count, and keep a running total. Update the total with
total = total - old + new. Then each letter costsO(1), and the time isO(N). The space is the number of different letters.- How is this different from Distinct Subsequences (LC 115)?
Distinct Subsequences (LC 115) counts how many ways a fixed string
tappears insides, so the state is a position int. Here no target is given. We count every different subsequence of one string, so the state is the last letter.- What is the time and space complexity?
O(26 * N), which is
O(N), time and O(26), which isO(1), space. Each letter does one sum over 26 numbers and one write. The result is reduced modulo 10^9 + 7.
SWE Reasoning
Spot it
- You count something over one string, and no second string is given to match against.
- The word "distinct" or "different" appears. Two choices of positions that give the same text must count once.
- The brute force lists subsets of positions and puts the texts in a set. That is 2^N subsets, which is too slow for 2000 letters.
- A new letter extends what exists, and the only fact you need about an old subsequence is its last letter.
- The alphabet is small and fixed (26 letters), so one count per letter is cheap.
The invariant, step by step
- Before the loop,
ends = [0] * 26. No subsequence has been built. - A letter
chis read. Its index isord(ch) - ord("a"). - Every subsequence built so far can be extended with
ch. There aresum(ends)of them. The letterchalone gives one more, so the new group hassum(ends) + 1subsequences. - This group contains every subsequence that already ended in
ch, because each one is a shorter subsequence plusch. So the oldends[ch]is replaced, not added to. - The code writes
ends[ch] = (sum(ends) + 1) % MOD. All other entries stay unchanged. - After the last letter, each different non-empty subsequence is counted once, in the entry of its last letter. So
sum(ends) % MODis the answer.
Traps
- Adding instead of replacing, on a string that is not one repeated letter. For
"aba", the secondamust giveendsforaequal to 4. Adding the old value 1 gives 5 there, and the final answer is 7 instead of 6. - Counting the empty string. The problem asks for non-empty subsequences. If you count the empty string as one more subsequence and do not remove it at the end,
"a"returns 2 instead of 1. - Using a set of strings. Storing every subsequence takes exponential memory. For a string of 2000 letters this cannot finish. Count by last letter instead.