Builds on Two-Sequence DP, which you haven’t finished yet.
Distinct Subsequences Counting DP
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.
s 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.Distinct Subsequences
t can be picked out of another string s, in order with gaps allowed, or how many distinct subsequences a string has: a count of subsequence matches, not one longest or cheapest alignment.| 1 | def num_distinct(s: str, t: str) -> int: |
| 2 | """Distinct Subsequences: count the ways t can be picked out of s, one character of s at a time. |
| 3 | Time: O(M * N) | Space: O(N) |
| 4 | """ |
| 5 | n = len(t) |
| 6 | ways = [1] + [0] * n # ways[j]: ways to spell t[:j] from the part of s read so far; t[:0] once, by picking nothing |
| 7 | Â |
| 8 | for ch in s: # Each character of s is either used or skipped |
| 9 | for j in range(n, 0, -1): # Backwards: ways[j - 1] still counts only the characters before ch |
| 10 | if t[j - 1] == ch: |
| 11 | ways[j] += ways[j - 1] # Old ways[j] skip ch; the ways[j - 1] ways finish t[:j] with ch |
| 12 | Â |
| 13 | return ways[n] |
s is read, ways[j] is the number of ways to spell t[:j] with the characters read so far, and ways[0] = 1.Read s one character ch at a time and keep ways[j], the number of ways to spell the first j letters of t with what you have read so far. A new ch changes nothing unless t[j - 1] == ch; then every way to spell t[:j - 1] can finish with ch, so ways[j] += ways[j - 1], while the old ways[j] stays counted as the ways that skip ch. Nothing else is needed, because each count already covers every way to use the characters read so far; ways[0] = 1 because the empty prefix is spelled once, by picking nothing. The trap is the direction of j: run it from n down to 1, so ways[j - 1] is read before this same ch changes it. Going up, one letter of s fills two places of t, and "rabbbit", "rabbit" returns 6 instead of 3.
See it run
Distinct Subsequences, step by step
ch -ways [1, 0, 0, 0, 0, 0, 0]
Row k is the list ways after the k-th letter of s. Column j counts the ways to spell t[:j].
newthe cell being written (also the starting cell ways[0])finishthe old ways[j - 1], which finishes t[:j] with this letterskipthe old ways[j], which skips this letteranswerthe final answer
Start: s = "rabbbit" and t = "rabbit". ways = [1] + [0] * 6. ways[0] = 1 because the empty prefix of t is spelled once, by picking nothing.
Gotcha 1 of 4
- The trap
Gotcha 1: Running
jupward instead of fromndown to 1Mistakefor j in range(1, n + 1):Fixfor j in range(n, 0, -1):What happens:
ways[j] += ways[j - 1]must readways[j - 1]from before the currentch. Going upward,ways[j - 1]was already changed by this samech. So one letter ofsfills two places oft.Example: s = "rabbbit", t = "rabbit"Mistake: returns 6Fix: returns 3
- The question asks for the length of the best match between two strings, as in Longest Common Subsequence (LC 1143), not for a count of the ways one string can be picked out of the other. See Two-Sequence DP
- There is no second string
tto match against, as in Distinct Subsequences II (LC 940): the question counts every distinct subsequence of one string, by a running count per last letter, not the ways to spell a fixed target. See Last-Char Counting DP
Deep Dive
The observation: count by the last letter of the prefix
The problem asks how many ways the string t can be picked out of s. A way is a set of positions in s, in increasing order, whose letters spell t. Two ways are different when their sets of positions are different, even if the letters are the same.
The observation is to read s one letter at a time and to count the ways for every prefix of t at once. ways[j] is the number of ways to spell t[:j] from the part of s read so far. The answer is ways[n] after the last letter.
Example: for s = "rabbbit" and t = "rabbit", the three b letters of s give three ways to pick the two b letters of t. That is why the answer is 3.
Why ways[j] += ways[j - 1] is correct
When a new letter ch is read, every way to spell t[:j] either skips ch or uses it as its last letter.
The ways that skip ch are the old ways[j]. They stay valid, so += keeps them.
The ways that use ch as the last letter exist only when t[j - 1] == ch. Each one is a way to spell t[:j - 1] from the earlier letters, followed by ch. Their number is ways[j - 1], read from before this ch.
The two groups share no way, because one uses the position of ch and the other does not. So the new ways[j] is the sum of the two groups.
ways[0] = 1 because the empty prefix is spelled one time, by picking nothing. Without it, every sum would start from 0.
What this card adds to Two-Sequence DP
Two-Sequence DP already teaches that a state is a pair of prefixes, one of s and one of t, and that a row depends only on the row above it. This card keeps that state and that row-by-row order.
The new part is the question. Two-Sequence DP takes the best value of neighbouring cells. This card adds the counts of two cells, because it counts ways.
In a table, the update is dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] when the letters match, and dp[i][j] = dp[i - 1][j] when they differ. The first term counts the ways that skip the letter. The second term counts the ways that use it.
One list ways holds the row. It is updated in place, and that is why the direction of j matters.
Why j runs from n down to 1, and the cost
The update for j reads ways[j - 1] from the row above. If j runs upward, ways[j - 1] was already changed by the same ch. One letter of s would then fill two places of t.
Running j downward changes ways[j] before ways[j - 1]. So ways[j - 1] still holds the value from before ch.
Example: s = "rabbbit", t = "rabbit" returns 3 with the downward loop and 6 with the upward loop. For s = "aaaa" and t = "aa", the correct answer is 6 and the upward loop returns 10.
There are M letters in s and N letters in t. Each pair is visited once with constant work, so the time is O(M * N). The list ways has N + 1 entries, so the space is O(N).
The count can grow quickly. LeetCode guarantees that the answer fits in a 32-bit integer. Python integers do not overflow, but in a language with fixed-size integers the intermediate values need the same guarantee.
60-Second Pitch
"The brute force chooses positions in s that spell t. That grows exponentially, so I count instead. I read s one letter at a time and keep ways[j], the number of ways to spell the first j letters of t so far, with ways[0] = 1. When the letter ch equals t[j - 1], every way to spell t[:j - 1] can end with ch. So I add ways[j - 1] to ways[j]. The old ways[j] stays, because it counts the ways that skip ch. I loop j from n down to 1, so ways[j - 1] is read before this letter changes it. That gives O(M * N) time and O(N) space. For s = "babgbag" and t = "bag", the answer is 5."
Common Questions
- Why does the inner loop run backwards?
The update for
jneedsways[j - 1]from before the current letter. Going backwards changesways[j]beforeways[j - 1], so the older value is still there. Going forwards lets one letter ofsfill two places oft.- How do you write this as a two-dimensional table?
Let
dp[i][j]be the ways to spellt[:j]froms[:i]. Setdp[i][0] = 1. Thendp[i][j] = dp[i - 1][j], plusdp[i - 1][j - 1]whens[i - 1] == t[j - 1]. The answer isdp[M][N]. The card's list keeps only one row, which is why the space isO(N)and not O(M * N).- What is the time and space complexity, and can the space be smaller?
O(M * N) time and
O(N)space, whereM = len(s)andN = len(t). IfNis larger thanM, the answer is 0, so the function can return at once. After that check,N <= M, so the list overtis the shorter one.- What does the function return when
tis longer thans, or whentis empty? When
tis longer thans, it returns 0, becausetcannot be spelled. Fors = "abc"andt = "abcd"the result is 0. Whentis empty, it returns 1, because picking nothing spells the empty string.- How is this different from Longest Common Subsequence (LC 1143) and Distinct Subsequences II (LC 940)?
Longest Common Subsequence (LC 1143) uses the same pair of prefixes but takes a maximum length, so each cell takes the best of its neighbours. This card keeps that state and changes only the combining step. Distinct Subsequences II (LC 940) has one string and counts different texts, so it keeps a count per last letter. This problem counts position sets that spell a fixed
t, so each cell adds counts.
SWE Reasoning
Spot it
- Two strings are given, and the question asks how many ways one is picked out of the other, not how long or how cheap the best match is.
- Order matters and gaps are allowed, so the picked letters form a subsequence of
s. - Different positions count as different ways, even when they spell the same text.
- The brute force chooses positions in
sand grows exponentially. The state(letters of s read, letters of t matched)has onlyM * Nvalues. - The answer is a sum over two disjoint cases: the current letter is used, or it is skipped.
The invariant, step by step
ways = [1] + [0] * nis set before any letter is read.ways[0] = 1, and every otherways[j]is 0 because no letter ofshas been read yet.- The loop reads one letter
chofs. At this momentways[j]is correct for alljfor the letters read beforech. - The inner loop visits
jfromndown to 1. For ajwheret[j - 1] == ch, it addsways[j - 1]toways[j]. - The old
ways[j]is kept. These are the ways that skipch. The added valueways[j - 1]is read beforechchanges it, because the loop goes downward and changesways[j - 1]only after it has finished withways[j]. - Each
jwheret[j - 1] != chis left unchanged. No new way ends withchthere. - After the last letter,
ways[j]counts the ways to spellt[:j]from the wholes.ways[n]is the answer. - Trace for
s = "babgbag"andt = "bag":waysafter each letter is [1,1,0,0], [1,1,1,0], [1,2,1,0], [1,2,1,1], [1,3,1,1], [1,3,4,1], [1,3,4,5]. The answer is 5.
Traps
jruns upward.ways[j - 1]was already changed by the samech, so one letter ofsis used for two letters oft.num_distinct("rabbbit", "rabbit")returns 6 instead of 3.=instead of+=. The oldways[j]holds the ways that skipch. Assignment throws them away.num_distinct("ccc", "c")returns 1 instead of 3.ways[0] = 0. The first match readsways[0]. With 0, every count stays 0. The same call returns 0.t[j]instead oft[j - 1].ways[j]ends with the lettert[j - 1]. Usingt[j]is off by one and raisesIndexErroratj = n.- Treating equal text as one way. The problem counts position sets. Two different sets of positions that spell
tare two ways. Removing duplicates gives a smaller, wrong answer. - Using this card for Distinct Subsequences II (LC 940). That problem has no target string
t. It counts different texts, so it needs a count per last letter and a replace step, not a prefix oft.
Practice
Builds on Two-Sequence DP, which you haven’t finished yet.
Distinct Subsequences Counting DP
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.
s 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.Distinct Subsequences
t can be picked out of another string s, in order with gaps allowed, or how many distinct subsequences a string has: a count of subsequence matches, not one longest or cheapest alignment.| 1 | def num_distinct(s: str, t: str) -> int: |
| 2 | """Distinct Subsequences: count the ways t can be picked out of s, one character of s at a time. |
| 3 | Time: O(M * N) | Space: O(N) |
| 4 | """ |
| 5 | n = len(t) |
| 6 | ways = [1] + [0] * n # ways[j]: ways to spell t[:j] from the part of s read so far; t[:0] once, by picking nothing |
| 7 | Â |
| 8 | for ch in s: # Each character of s is either used or skipped |
| 9 | for j in range(n, 0, -1): # Backwards: ways[j - 1] still counts only the characters before ch |
| 10 | if t[j - 1] == ch: |
| 11 | ways[j] += ways[j - 1] # Old ways[j] skip ch; the ways[j - 1] ways finish t[:j] with ch |
| 12 | Â |
| 13 | return ways[n] |
s is read, ways[j] is the number of ways to spell t[:j] with the characters read so far, and ways[0] = 1.Read s one character ch at a time and keep ways[j], the number of ways to spell the first j letters of t with what you have read so far. A new ch changes nothing unless t[j - 1] == ch; then every way to spell t[:j - 1] can finish with ch, so ways[j] += ways[j - 1], while the old ways[j] stays counted as the ways that skip ch. Nothing else is needed, because each count already covers every way to use the characters read so far; ways[0] = 1 because the empty prefix is spelled once, by picking nothing. The trap is the direction of j: run it from n down to 1, so ways[j - 1] is read before this same ch changes it. Going up, one letter of s fills two places of t, and "rabbbit", "rabbit" returns 6 instead of 3.
See it run
Distinct Subsequences, step by step
ch -ways [1, 0, 0, 0, 0, 0, 0]
Row k is the list ways after the k-th letter of s. Column j counts the ways to spell t[:j].
newthe cell being written (also the starting cell ways[0])finishthe old ways[j - 1], which finishes t[:j] with this letterskipthe old ways[j], which skips this letteranswerthe final answer
Start: s = "rabbbit" and t = "rabbit". ways = [1] + [0] * 6. ways[0] = 1 because the empty prefix of t is spelled once, by picking nothing.
Gotcha 1 of 4
- The trap
Gotcha 1: Running
jupward instead of fromndown to 1Mistakefor j in range(1, n + 1):Fixfor j in range(n, 0, -1):What happens:
ways[j] += ways[j - 1]must readways[j - 1]from before the currentch. Going upward,ways[j - 1]was already changed by this samech. So one letter ofsfills two places oft.Example: s = "rabbbit", t = "rabbit"Mistake: returns 6Fix: returns 3
- The question asks for the length of the best match between two strings, as in Longest Common Subsequence (LC 1143), not for a count of the ways one string can be picked out of the other. See Two-Sequence DP
- There is no second string
tto match against, as in Distinct Subsequences II (LC 940): the question counts every distinct subsequence of one string, by a running count per last letter, not the ways to spell a fixed target. See Last-Char Counting DP
Deep Dive
The observation: count by the last letter of the prefix
The problem asks how many ways the string t can be picked out of s. A way is a set of positions in s, in increasing order, whose letters spell t. Two ways are different when their sets of positions are different, even if the letters are the same.
The observation is to read s one letter at a time and to count the ways for every prefix of t at once. ways[j] is the number of ways to spell t[:j] from the part of s read so far. The answer is ways[n] after the last letter.
Example: for s = "rabbbit" and t = "rabbit", the three b letters of s give three ways to pick the two b letters of t. That is why the answer is 3.
Why ways[j] += ways[j - 1] is correct
When a new letter ch is read, every way to spell t[:j] either skips ch or uses it as its last letter.
The ways that skip ch are the old ways[j]. They stay valid, so += keeps them.
The ways that use ch as the last letter exist only when t[j - 1] == ch. Each one is a way to spell t[:j - 1] from the earlier letters, followed by ch. Their number is ways[j - 1], read from before this ch.
The two groups share no way, because one uses the position of ch and the other does not. So the new ways[j] is the sum of the two groups.
ways[0] = 1 because the empty prefix is spelled one time, by picking nothing. Without it, every sum would start from 0.
What this card adds to Two-Sequence DP
Two-Sequence DP already teaches that a state is a pair of prefixes, one of s and one of t, and that a row depends only on the row above it. This card keeps that state and that row-by-row order.
The new part is the question. Two-Sequence DP takes the best value of neighbouring cells. This card adds the counts of two cells, because it counts ways.
In a table, the update is dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] when the letters match, and dp[i][j] = dp[i - 1][j] when they differ. The first term counts the ways that skip the letter. The second term counts the ways that use it.
One list ways holds the row. It is updated in place, and that is why the direction of j matters.
Why j runs from n down to 1, and the cost
The update for j reads ways[j - 1] from the row above. If j runs upward, ways[j - 1] was already changed by the same ch. One letter of s would then fill two places of t.
Running j downward changes ways[j] before ways[j - 1]. So ways[j - 1] still holds the value from before ch.
Example: s = "rabbbit", t = "rabbit" returns 3 with the downward loop and 6 with the upward loop. For s = "aaaa" and t = "aa", the correct answer is 6 and the upward loop returns 10.
There are M letters in s and N letters in t. Each pair is visited once with constant work, so the time is O(M * N). The list ways has N + 1 entries, so the space is O(N).
The count can grow quickly. LeetCode guarantees that the answer fits in a 32-bit integer. Python integers do not overflow, but in a language with fixed-size integers the intermediate values need the same guarantee.
60-Second Pitch
"The brute force chooses positions in s that spell t. That grows exponentially, so I count instead. I read s one letter at a time and keep ways[j], the number of ways to spell the first j letters of t so far, with ways[0] = 1. When the letter ch equals t[j - 1], every way to spell t[:j - 1] can end with ch. So I add ways[j - 1] to ways[j]. The old ways[j] stays, because it counts the ways that skip ch. I loop j from n down to 1, so ways[j - 1] is read before this letter changes it. That gives O(M * N) time and O(N) space. For s = "babgbag" and t = "bag", the answer is 5."
Common Questions
- Why does the inner loop run backwards?
The update for
jneedsways[j - 1]from before the current letter. Going backwards changesways[j]beforeways[j - 1], so the older value is still there. Going forwards lets one letter ofsfill two places oft.- How do you write this as a two-dimensional table?
Let
dp[i][j]be the ways to spellt[:j]froms[:i]. Setdp[i][0] = 1. Thendp[i][j] = dp[i - 1][j], plusdp[i - 1][j - 1]whens[i - 1] == t[j - 1]. The answer isdp[M][N]. The card's list keeps only one row, which is why the space isO(N)and not O(M * N).- What is the time and space complexity, and can the space be smaller?
O(M * N) time and
O(N)space, whereM = len(s)andN = len(t). IfNis larger thanM, the answer is 0, so the function can return at once. After that check,N <= M, so the list overtis the shorter one.- What does the function return when
tis longer thans, or whentis empty? When
tis longer thans, it returns 0, becausetcannot be spelled. Fors = "abc"andt = "abcd"the result is 0. Whentis empty, it returns 1, because picking nothing spells the empty string.- How is this different from Longest Common Subsequence (LC 1143) and Distinct Subsequences II (LC 940)?
Longest Common Subsequence (LC 1143) uses the same pair of prefixes but takes a maximum length, so each cell takes the best of its neighbours. This card keeps that state and changes only the combining step. Distinct Subsequences II (LC 940) has one string and counts different texts, so it keeps a count per last letter. This problem counts position sets that spell a fixed
t, so each cell adds counts.
SWE Reasoning
Spot it
- Two strings are given, and the question asks how many ways one is picked out of the other, not how long or how cheap the best match is.
- Order matters and gaps are allowed, so the picked letters form a subsequence of
s. - Different positions count as different ways, even when they spell the same text.
- The brute force chooses positions in
sand grows exponentially. The state(letters of s read, letters of t matched)has onlyM * Nvalues. - The answer is a sum over two disjoint cases: the current letter is used, or it is skipped.
The invariant, step by step
ways = [1] + [0] * nis set before any letter is read.ways[0] = 1, and every otherways[j]is 0 because no letter ofshas been read yet.- The loop reads one letter
chofs. At this momentways[j]is correct for alljfor the letters read beforech. - The inner loop visits
jfromndown to 1. For ajwheret[j - 1] == ch, it addsways[j - 1]toways[j]. - The old
ways[j]is kept. These are the ways that skipch. The added valueways[j - 1]is read beforechchanges it, because the loop goes downward and changesways[j - 1]only after it has finished withways[j]. - Each
jwheret[j - 1] != chis left unchanged. No new way ends withchthere. - After the last letter,
ways[j]counts the ways to spellt[:j]from the wholes.ways[n]is the answer. - Trace for
s = "babgbag"andt = "bag":waysafter each letter is [1,1,0,0], [1,1,1,0], [1,2,1,0], [1,2,1,1], [1,3,1,1], [1,3,4,1], [1,3,4,5]. The answer is 5.
Traps
jruns upward.ways[j - 1]was already changed by the samech, so one letter ofsis used for two letters oft.num_distinct("rabbbit", "rabbit")returns 6 instead of 3.=instead of+=. The oldways[j]holds the ways that skipch. Assignment throws them away.num_distinct("ccc", "c")returns 1 instead of 3.ways[0] = 0. The first match readsways[0]. With 0, every count stays 0. The same call returns 0.t[j]instead oft[j - 1].ways[j]ends with the lettert[j - 1]. Usingt[j]is off by one and raisesIndexErroratj = n.- Treating equal text as one way. The problem counts position sets. Two different sets of positions that spell
tare two ways. Removing duplicates gives a smaller, wrong answer. - Using this card for Distinct Subsequences II (LC 940). That problem has no target string
t. It counts different texts, so it needs a count per last letter and a replace step, not a prefix oft.