Distinct Subsequences

1. The obvious way

   Recursion choosing to use or skip each letter: O(2^n).

2. The key insight

   ways[k] = number of ways to form the first k letters of t from the part of s seen so far. ways[0] = 1. For each letter of s, for k from len(t) down to 1: if t[k - 1] equals this letter, ways[k] += ways[k - 1]. Answer ways[len(t)].

3. The algorithm
   1. ways[0] = 1, others 0.
   2. For each source letter, go through the prefixes from longest to shortest.
   3. If the prefix ends with this letter, add the ways of the shorter prefix.
   4. Return ways[len(t)].

Watch it run

ra: 1

def num_distinct(s, t):
    ways = [1] + [0] * len(t)                            # ways[k]: spell the first k letters of t
    for letter in s:
        for taken in range(len(t), 0, -1):               # longest prefix first: use each letter once
            if t[taken - 1] == letter:
                ways[taken] += ways[taken - 1]
    return ways[len(t)]

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.