The problem
Count the number of ways to delete letters from string s (keeping the order of the rest) so that what remains is exactly string t.
Input: s = "rabbbit", t = "rabbit" Output: 3
Picture it
Picture crossing out letters of the long word with a pen. The table cell (i, j) counts the ways to make the first j letters of t from the first i letters of s. At each letter of s we can skip it (take the count above). If it matches the current letter of t, we may also use it (add the diagonal count).
How to recognise it
- You count how many ways one string can be produced from another by deleting letters, keeping the order.
- Equal letters in different positions count as different ways.
- Looking at the last letter of the long string gives two simple choices: skip it or use it.
- The two strings are up to 1000 letters long, so the number of choices is astronomical.
- The count, not the ways themselves, is requested.
Start with brute force
Choose which len(t) positions of s to keep, read the letters in order, and count the choices that spell t.
from itertools import combinations
def num_distinct_brute(s, t):
count = 0
for pos in combinations(range(len(s)), len(t)):
if "".join(s[i] for i in pos) == t:
count += 1
return count
There are C(m, n) choices (m = len(s), n = len(t)), each costing O(n) to check. For m = 1000 and n = 500 that is about 2.7 × 10^299 choices. Space is O(n).
From brute force to the idea
- Look at the last letter of
s. Either that letter is not used, or it is used to match the last letter oft. - Not used: the ways are the same as for
swithout its last letter:ways[i-1][j]. - Used (only if
s[i-1] == t[j-1]): the rest oftmust come from the earlier letters ofs: addways[i-1][j-1]. - Build the table.
ways[i][j]is the number of ways to make the first j letters oftfrom the first i letters ofs. The two cases above are added, because they are different ways. - Base cases. Column 0 is all 1: crossing out everything leaves the empty word in exactly one way. Row 0 below that is 0, since an empty
scannot make a non-emptyt. - Read the answer. The bottom-right cell is the result.
This is the key idea: every way is either "skip this letter" or "use this letter", and both counts come from smaller prefixes.
The key idea
dp[i][j] = dp[i−1][j] + (dp[i−1][j−1] if s[i−1] == t[j−1]). O(m × n).
Python solution
def num_distinct(s, t):
ways = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s) + 1):
ways[i][0] = 1 # empty t: cross out everything
for i in range(1, len(s) + 1):
for j in range(1, len(t) + 1):
ways[i][j] = ways[i - 1][j] # skip s[i-1]
if s[i - 1] == t[j - 1]:
ways[i][j] += ways[i - 1][j - 1] # or use it
return ways[len(s)][len(t)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(C(m, n) · n): every set of kept positions is checked | O(n): one candidate word |
| DP table (shown code) | O(m · n): one addition or two per cell | O(m · n): the table; one row of length n + 1 would be enough |
For two strings of length 1000 that is about a million cells.
Edge cases
- Empty
t: returns 1 for anys, including the empty string (num_distinct("abc", "")is 1). - Empty
s, non-emptyt: returns 0. tlonger thans: returns 0 (("ab", "abc")).- Equal strings: returns 1.
- Repeated letters (
"aaaa","aa"): returns 6, which is C(4, 2). Every pair of positions is a different way. - No matching letters (
"abc","abd"): returns 0. - Large answers: Python integers do not overflow. For
sof 1000 letters, the count can have hundreds of digits in principle, but the problem promises it fits in 32 bits.
Common mistakes
- Writing the recurrence as "use it or skip it" with an if/else, so a matching letter loses its "skip" ways (see the quiz).
- Forgetting the column-0 base case, so every answer is 0.
- Using
maxinstead of a sum, which finds whether a way exists, not how many. - Indexing
s[i]instead ofs[i - 1]because the table has an extra row and column.
Keep the same recurrence but use only one list of length len(t) + 1 instead of the full table. For "rabbbit" and "rabbit" the answer must still be 3. Describe your approach, then write it if you like.
Compare with our answer
The new row needs ways[i-1][j] (the same slot, before updating) and ways[i-1][j-1] (the slot to its left, before updating). If you update from left to right, the left slot has already been overwritten. So go through j from right to left.
def num_distinct_one_row(s, t):
ways = [1] + [0] * len(t) # ways[j]: first j letters of t
for ch in s:
for j in range(len(t), 0, -1): # right to left keeps old values
if ch == t[j - 1]:
ways[j] += ways[j - 1]
return ways[len(t)]
It returns 3 for ("rabbbit", "rabbit"), 5 for ("babgbag", "bag") and 1 for an empty t. Going left to right instead would give 6 for ("aaa", "aa"), not 3. Time O(m · n), space O(n).
A strong answer mentions: the skip case being "keep the old value", the right-to-left order, and why left-to-right reuses a letter twice.
1. You need the number of ways to choose positions in string S whose letters, in order, spell a word W. Which approach fits best?
The letters need not be adjacent and every choice of positions counts separately, so skip and use counts are added over prefix pairs. A window counts only contiguous matches, and LCS gives a length, not a count.
2. Why is the first column of the table set to 1 and not 0?
ways[i][0] is the number of ways to make the empty word from i letters, and that is one way (cross out all). That one way seeds every later count. The code adds counts, never multiplies them.
3. A learner rewrites the inner step as if s[i-1] == t[j-1]: ways[i][j] = ways[i-1][j-1] with an else: ways[i][j] = ways[i-1][j]. What does num_distinct("rabbbit", "rabbit") return?
When letters match, the correct code adds the skip count and the use count; the variant keeps only the use count and loses the other ways. Running the variant gives 1 where the right answer is 3.
Score 60% or more and the lesson is marked complete.