LeetCode 115 · 2-D DP

Distinct Subsequences, explained with a picture

How many ways to cross out letters and leave a word.

Hard2-D DP
▶ Watch it step by step

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

  1. Look at the last letter of s. Either that letter is not used, or it is used to match the last letter of t.
  2. Not used: the ways are the same as for s without its last letter: ways[i-1][j].
  3. Used (only if s[i-1] == t[j-1]): the rest of t must come from the earlier letters of s: add ways[i-1][j-1].
  4. Build the table. ways[i][j] is the number of ways to make the first j letters of t from the first i letters of s. The two cases above are added, because they are different ways.
  5. 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 s cannot make a non-empty t.
  6. 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

ApproachTimeSpace
Brute forceO(C(m, n) · n): every set of kept positions is checkedO(n): one candidate word
DP table (shown code)O(m · n): one addition or two per cellO(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 any s, including the empty string (num_distinct("abc", "") is 1).
  • Empty s, non-empty t: returns 0.
  • t longer than s: 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 s of 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 max instead of a sum, which finds whether a way exists, not how many.
  • Indexing s[i] instead of s[i - 1] because the table has an extra row and column.
Your turn: one row only

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.

Check what stuck

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?

2. Why is the first column of the table set to 1 and not 0?

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?

Score 60% or more and the lesson is marked complete.