Distinct Subsequences

The problem

You are given two strings, s and t. Pick some positions of s and read the letters at those positions from left to right; letters picked this way are called a subsequence of s. Return how many different sets of positions spell exactly t. Two sets that use different positions count separately, even when their letters are the same. An empty t is spelled in exactly one way, by picking nothing, so then the answer is 1. If no set of positions spells t, return 0.

What to write

function solve(s: string, t: string): number

Input
s = "rabbbit"
t = "rabbit"

Output
3

Input
s = "babgbag"
t = "bag"

Output
5

Constraints

The final answer fits a signed 32-bit integer; strings may be empty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The answer only has to fit in a signed 32-bit integer, so it can be as large as about two billion. Listing the ways one by one is hopeless at that size. You need to count the ways without building each of them. Note also that either string may be empty.

2. Hint 2: Ask a smaller question

   Count by hand the ways to spell ba from bab. Now add one letter: baba. Every new way must use that last a. What do the letters before it have to spell, and in how many ways could bab already do that?

3. Hint 3: Name the pattern

   Two things change as you go: how many letters of s you have read, and how long a prefix of t (its first few letters) you have spelled. A count for every such pair, built from the counts for smaller pairs, is two-dimensional dynamic programming. Each row of counts needs only the row before it, so one row is enough. Read the lesson on two-dimensional dynamic programming.

4. Hint 4: State the invariant

   After some letters of s are read, the count for a prefix of t is the number of ways to spell that prefix with letters chosen from the part of s read so far. A new letter that equals the prefix's last letter adds the earlier count of the prefix one letter shorter. Otherwise the count stays.

5. Hint 5: Sketch the pseudocode

   ways = a list of zeros with one entry per prefix of t, the empty prefix included. ways[0] = 1. For each letter of s: for j from the length of t down to 1: if the letter equals letter j of t, add ways[j - 1] to ways[j]. Return the last entry of ways.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Each matching character may extend a shorter match. Update target positions backward to avoid reusing the same source character.

The slow way

At each letter of s, either skip it or, when it is the next letter t still needs, use it. Follow both choices and count the ones that finish t. It is correct, but it walks to every way one at a time. With 20 a's in s and 10 a's in t the answer is 184,756, and this search makes 1,233,331 calls. The method below makes 200 comparisons.

The insight

Look at the newest letter of s. Every way to spell a prefix of t, meaning its first few letters, either leaves that letter out or uses it as the prefix's last letter. Leaving it out: the ways counted before. Using it needs a match, and the letters before must spell the prefix one letter shorter. New count: old count plus, on a match, the shorter prefix's old count.

Step by step

1. Keep a count for every prefix of t, from no letters to all of them. The count for a prefix is the number of ways to spell it with letters chosen from the part of s read so far. Nothing is read yet, so every prefix that has letters starts at 0.
2. The empty prefix can be spelled in one way: by choosing nothing. Spelling no letters needs no letters of s, and there is exactly one way to choose nothing. Every other count grows out of this 1. Without it, all counts stay 0.
3. Read s one letter at a time. A new letter never removes a way, because any way may leave it out. It can only add the ways that use it as their last letter. So the counts are updated once per letter.
4. Go through the prefixes of t from the longest to the shortest. An update reads the count of the prefix one letter shorter, and it needs the value from before this letter of s. Going from long to short reads every shorter count before it changes.
5. A letter that ends a prefix adds the count of the shorter prefix. When the letter equals the prefix's last letter, it can be that last letter. The letters chosen before it must spell the prefix one letter shorter, and the shorter count says in how many ways.
6. The count for the whole of t is the answer. After the last letter, every count covers all of s. The last one counts the ways to spell every letter of t, which is what was asked.

The same numbered steps are the comments in each solution.

function solve(s, t) {
  // 1. Keep a count for every prefix of t, from no letters to all of them
  const dp = Array(t.length + 1).fill(0);
  // 2. The empty prefix can be spelled in one way: by choosing nothing
  dp[0] = 1;
  // 3. Read s one letter at a time
  for (const ch of s) {
    // 4. Go through the prefixes of t from the longest to the shortest
    for (let j = t.length; j > 0; j--) {
      // 5. A letter that ends a prefix adds the count of the shorter prefix
      if (ch === t[j - 1]) dp[j] += dp[j - 1];
    }
  }
  // 6. The count for the whole of t is the answer
  return dp[t.length];
}

function solve(s: string, t: string): number {
  // 1. Keep a count for every prefix of t, from no letters to all of them
  const dp = Array(t.length + 1).fill(0);
  // 2. The empty prefix can be spelled in one way: by choosing nothing
  dp[0] = 1;
  // 3. Read s one letter at a time
  for (const ch of s) {
    // 4. Go through the prefixes of t from the longest to the shortest
    for (let j = t.length; j > 0; j--) {
      // 5. A letter that ends a prefix adds the count of the shorter prefix
      if (ch === t[j - 1]) dp[j] += dp[j - 1];
    }
  }
  // 6. The count for the whole of t is the answer
  return dp[t.length];
}

def solve(s, t):
    # 1. Keep a count for every prefix of t, from no letters to all of them
    dp = [0] * (len(t) + 1)
    # 2. The empty prefix can be spelled in one way: by choosing nothing
    dp[0] = 1
    # 3. Read s one letter at a time
    for char in s:
        # 4. Go through the prefixes of t from the longest to the shortest
        for j in range(len(t), 0, -1):
            # 5. A letter that ends a prefix adds the count of the shorter prefix
            if char == t[j - 1]:
                dp[j] += dp[j - 1]
    # 6. The count for the whole of t is the answer
    return dp[len(t)]

Example 1, traced

Input
s = "rabbbit"
t = "rabbit"

Output
3

Why it works

Before a letter is read, each count is right for the letters read so far. With the new letter, a way to spell a prefix either leaves that letter out, which the old count covers, or ends with it, which the shorter prefix's old count covers. No way is in both groups, so adding them counts every way exactly once. Going from long to short keeps the old counts readable.

Time and space

Time O(m n), extra space O(n). Call the length of s m and the length of t n. Each letter of s goes through all n prefixes with one comparison each, so the time is O(m n). Only one list of n + 1 counts is stored: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Go from the longest prefix to the shortest. In the other direction one letter can be used twice: the first b of example 1 completes rab and then, in the same round, rabb. Example 1 returns 6 instead of 3.
• Set the count of the empty prefix to 1 before the loop. If it stays 0, every other count stays 0 too, and the answer is 0 for every input, even for an empty t, where it should be 1.
• Add to the count; do not replace it. The ways that leave the new letter out are still valid. Replacing the count with the shorter prefix's count makes example 1 return 1 instead of 3.

Pattern

Two-dimensional dynamic programming. Builds on Longest Common Subsequence and Partition Equal Subset Sum.

Keep going