Distinct subsequences and counting paths in Python strings

Why this matters

Many searches ask whether some letters appear in a string in a given order, without caring whether they sit next to each other. A log search for the words disk, full in that order is one example. Counting the ways a short string can be picked out of a longer one is another. The counting form of this search is a common interview question, and it teaches a pattern that shows up in many table problems: each new character either takes part in the answer or it does not.

This lesson counts the ways. The table has the same shape as the table in the previous lesson on regular expression matching, but each cell holds a number instead of True or False. The decode ways lesson earlier in this module also counts with a table. The one-row version of this table is shown near the end.

Every program in this lesson is a complete Python file. Save it as subseq.py and run it with python3 subseq.py. The outputs shown were produced on Python 3.14.4.

Words you need first

A subsequence is a set of letters taken from a string in order. The letters do not have to be next to each other. They only have to keep their order.

The word ace is a subsequence of abcde, because a, c and e appear in that order. The word aec is not, because e comes after c in abcde. The word ace is also a subsequence of aXcYe, because the letters X and Y can be skipped.

A substring is different. Its letters must sit next to each other in the string. The word bcd is a substring of abcde. The word ace is not a substring of abcde, because the letters are not adjacent. Python's in operator checks for a substring, so "ace" in "abcde" is False.

A position is the index of a letter in the string. In Python, positions start at 0. In the word abc, the letter b is at position 1.

A pick is a set of positions in the longer string that spell the shorter string.

The problem

The task has two strings. The longer one is called s, and the shorter one, which must be spelled out, is called t. The question is how many picks in s spell t.

Take s equal to rabbbit and t equal to rabbit. The string s has seven letters:

The string t has the letters r, a, b, b, i, t. The three b letters in s are at positions 2, 3 and 4. Two of them are needed. Each pair of them gives one pick. There are three pairs: positions 2 and 3, positions 2 and 4, or positions 3 and 4. So there are three picks. The program later in this lesson prints all three.

The three picks, as lists of positions, are these.

[0, 1, 3, 4, 5, 6]
[0, 1, 2, 4, 5, 6]
[0, 1, 2, 3, 5, 6]

The answer is the count of picks, which is 3. Two picks count as two even when they spell the same letters. In this lesson, two picks count as different when they use different positions. The spelled strings may be the same.

The count can become very large for long inputs. Python integers have no fixed size. A count keeps every digit it needs, so this lesson needs no overflow check. A fixed 64-bit integer wraps around once the count passes about 9.2 times 10 to the 18th, so languages that use one need an extra check. Problems that ask for the count modulo a fixed number, such as 10^9 + 7, keep the numbers small by taking a remainder after each step.

Step 1: each letter has one of two choices

Read s from left to right. For each letter, there are two choices.

• Skip it. The letter does not take part in the pick.
• Use it. The letter takes the next unmatched letter of t. This is allowed only when the two letters are the same.

For s equal to aab and t equal to ab, the choices work out as follows. The first a can be skipped or used for the a of t. The second a can be skipped or used for the same a of t, but only if the first a was skipped. The b can be used for the b of t if the a of t has already been matched. Two picks spell ab: positions 0 and 2, and positions 1 and 2.

This choice-by-choice view leads straight to code that tries every pick. That code is correct, but it is slow. A string of 30 letters has up to 2 to the power 30 choices for its letters, which is over a billion. The table below avoids that by reusing the answers for shorter prefixes.

Step 2: the table

Define dp[i][j] as the number of picks in the first i letters of s that spell the first j letters of t. Row i is a prefix of s. Column j is a prefix of t. The answer is the bottom right cell, dp[m][n], where m is the length of s and n is the length of t.

Set the base cases first.

Column 0 is the empty prefix of t. The empty string appears in any prefix of s in exactly one way, by picking nothing. So dp[i][0] is 1 for every i, including i equal to 0.

Row 0 is the empty prefix of s. Nothing can be picked from it, so dp[0][j] is 0 for every j above 0.

These two rules are the base cases. Setting column 0 to 0 instead is a common mistake, and the mistakes section shows what it does.

Step 3: the recurrence for each letter match

Take the cell dp[i][j]. The last letter of the s prefix is s[i - 1]. Call it c. The last letter of the t prefix is t[j - 1]. There are two sorts of pick to count.

• Picks that do not use c. These picks are exactly the picks that spell the t prefix inside the s prefix without the last letter. Their count is dp[i - 1][j].
• Picks that do use c for the last letter of t. This is possible only when c equals t[j - 1]. In that case the remaining letters must spell the shorter t prefix inside the shorter s prefix, which has count dp[i - 1][j - 1].

So the recurrence is:

dp[i][j] = dp[i - 1][j]
           + (dp[i - 1][j - 1] if s[i - 1] equals t[j - 1], else 0)

When the letters do not match, the second part is 0, and the cell only copies the cell above it. That is the skip choice alone.

Here is a short example. Take s equal to bb and t equal to b. The table has two rows and two columns of values, plus the base cells.

For the cell at row 1, column 1, the last letter of s is b, which equals the b of t. So the cell is dp[0][1], which is 0, plus dp[0][0], which is 1. The result is 1. That is the pick of the first b.

For the cell at row 2, column 1, the last letter of s is b again. The cell is dp[1][1], which is 1, plus dp[1][0], which is 1. The result is 2. The two picks are the first b and the second b. The first pick is the one counted in the row above, and the second pick is the one that uses the new b.

Worked example 1: babgbag and bag

The program prints the full table for s equal to babgbag and t equal to bag. The table has eight rows for the empty prefix of s and each of its seven letters. It has four columns for the empty prefix of t and each of its three letters. The columns are target prefixes: the first is the empty target, the second is b, the third is ba, and the fourth is bag. The printed headers show the last letter of each prefix.

         ''   b   a   g
   ''     1   0   0   0
    b     1   1   0   0
    a     1   1   1   0
    b     1   2   1   0
    g     1   2   1   1
    b     1   3   1   1
    a     1   3   4   1
    g     1   3   4   5

Start at the top row. The cell for the empty s and the empty t is 1, the base case. The cells to its right are 0, because a non-empty t cannot be spelled from nothing.

Now look at row b, the prefix b. The cell for b in t is 1. The last letter of the s prefix is b, which equals b. The skip part is dp[0][1], which is 0. The use part is dp[0][0], which is 1. The total is 1.

Look at the cell in row a, the prefix ba, in column ba. The cell is 1. The last letter of s is a, which matches the a of t. The skip part is dp[1][2], which is 0. The use part is dp[1][1], which is 1. The total is 1, and the only pick is the b at position 0 and the a at position 1.

Now look at the cell in row b, the prefix bab, in column b. The cell is 2. The last letter of s is b, which matches the b of t. The skip part is dp[2][1], which is 1. That is the pick of the first b, which is still available without the new b. The use part is dp[2][0], which is 1. That is the pick of the new b. The total is 2.

The last few cells show the same pattern. Take row a, the prefix babgba, in column ba. The cell is 4. The skip part is dp[5][2], which is 1. The use part is dp[5][1], which is 3, because the prefix babgb has three picks of b. The total is 1 + 3 = 4.

The bottom right cell is the answer. Take row g, the full s, in column bag. The skip part is dp[6][3], which is 1, because the prefix babgba has one pick of bag. The use part is dp[6][2], which is 4, because the prefix babgba has four picks of ba, and the new g completes each of them. The total is 1 + 4 = 5. The program prints 5 for this input.

Counting paths in strings

The title of this lesson mentions paths. The table gives a picture for that word.

Draw the table as a grid. Start at the top left corner, which is the empty prefix of both strings. Move down one row for each letter of s. A move that keeps the same column is a skip. A move that goes down and to the right is a use, and it is allowed only when the letter of s matches the letter of t for that column.

Each complete walk from the top left corner to the bottom right corner is one pick. The walk moves right exactly as many times as there are letters in t, and each right move happens on a matching letter. So the number of walks is the number of picks. The table fills in that count one cell at a time, from the top left, so the answer for each cell uses only the cells above and to the left of it.

This picture also explains the recurrence. The cell dp[i][j] collects walks that arrive from directly above, which are skips, and walks that arrive diagonally from above and to the left, which are uses.

Worked example 2: a short check with a repeated letter

Take s equal to aaa and t equal to a. The answer is 3, because each of the three a letters can be the one picked. Check that the table gives the same answer.

The row for the empty s is 1, 0, as before. The row for the first a uses the skip part, which is 0, plus the use part, which is 1 for column a. So that cell is 1.

The row for the second a in column a has skip part 1 and use part 1. So the cell is 2. The row for the third a in column a has skip part 2 and use part 1. So the cell is 3. The bottom right cell is 3, which matches the count of three single-letter picks.

The same table handles a longer t. For s equal to aaa and t equal to aa, the answer is also 3, because each pair of the three a letters is one pick. Calling num_distinct("aaa", "aa") returns 3 as well.

The Python program

The program below contains the table function, the one-row version, a brute force function that tries every pick, a function that lists the picks, and a table printer. The brute force function is slow for long inputs, but it gives a clear check for short ones. The one-row version is explained in its own section below.

The lines under if __name__ == "__main__": run only when the file is run directly. The last lines of the program count the ways that 100 a letters appear in 200 a letters. The answer has 59 digits, and Python stores every one of them. math.comb(200, 100) computes the same number directly, and the check prints True.

Run it with python3 subseq.py. The output below was produced by that exact file.

num_distinct:
  num_distinct("rabbbit", "rabbit") = 3
  num_distinct("babgbag", "bag") = 5
  num_distinct("abc", "abcd") = 0
  num_distinct("aaa", "a") = 3
  num_distinct("ab", "") = 1
  num_distinct("", "a") = 0
 
table for babgbag vs bag:
         ''   b   a   g
   ''     1   0   0   0
    b     1   1   0   0
    a     1   1   1   0
    b     1   2   1   0
    g     1   2   1   1
    b     1   3   1   1
    a     1   3   4   1
    g     1   3   4   5
 
index picks for rabbbit vs rabbit:
  [0, 1, 3, 4, 5, 6]
  [0, 1, 2, 4, 5, 6]
  [0, 1, 2, 3, 5, 6]
 
one-row version and brute force agree:
  rabbbit / rabbit: table=3 row=3 brute=3
  babgbag / bag: table=5 row=5 brute=5
  aaaaa / aaa: table=10 row=10 brute=10
  abcabc / abc: table=4 row=4 brute=4
  xyz / abc: table=0 row=0 brute=0
 
digits in the answer for 200 a and 100 a: 59
equals math.comb(200, 100): True

The print_table function prints the s letters on the left and the t letters across the top, the same way the regular expression lesson prints its table. The cell values line up under the letters of t.

The one-row version

Each row of the table depends only on the row above it. So the table can be squeezed into one list of length n + 1, the same trick used for one-dimensional tables in the earlier lessons of this module.

The order of the inner loop matters. The code runs j from n down to 1. When it updates dp[j], it reads dp[j - 1]. Going downward, dp[j - 1] has not been changed yet for this letter of s, so it still holds the old row. That is the value the recurrence needs.

If the loop ran upward, dp[j - 1] would already include the current letter. The same letter would then be used twice in one pick. The mistakes section shows a real wrong answer from that mistake.

Common mistakes

Forgetting the skip. A common version of the code only counts the use part when the letters match. It sets dp[i][j] to dp[i - 1][j - 1] in the matching case and to dp[i - 1][j] in the other case. That misses the picks that skip a matching letter. Here is the output from that version, next to the correct answers.

no_skip rabbbit/rabbit = 1
correct rabbbit/rabbit = 3
no_skip babgbag/bag = 1

For rabbbit, the version counts exactly one pick, the one that always takes the earliest matching letter. It misses the two picks that skip one of the early b letters.

Setting the empty-prefix base to 0. If the column for the empty t is 0 instead of 1, every cell that builds on it becomes 0, so the whole table is 0. The next output comes from a copy of the table with column 0 left at its starting value.

zero base rabbbit/rabbit = 0
zero base aaa/a = 0

The correct values are 3 and 3. The fix is the loop that sets dp[i][0] to 1 for every row.

Running the one-row version with the inner loop going up. The loop must run from high to low. Here is the output from a copy with the loop turned around.

upward aaa/aa = 6
correct aaa/aa = 3

The correct answer for aaa and aa is 3, because the pairs are positions 0 and 1, 0 and 2, and 1 and 2. The upward loop gives 6, because it lets the same a count twice.

Reading the current letter instead of the previous one. The table uses s[i - 1], the letter that the row stands for. Writing s[i] moves the read one letter ahead. The last row then asks for a letter past the end of the string. Python stops with this error.

Traceback (most recent call last):
  ...
    if s[i] == t[j - 1]:
       ~^^^
IndexError: string index out of range

The first lines of the traceback are shortened here. The fix is to use s[i - 1] on both sides of the comparison.

Confusing a subsequence with a substring. A substring must sit in one block of adjacent letters. A subsequence can skip letters. The program gives a different answer for each idea. Take s equal to xaxb and t equal to ab. The program prints 1 for num_distinct("xaxb", "ab"), because the pick uses position 1 for a and position 3 for b. The word ab is not a substring of xaxb, because the two letters are separated by an x. Python's in operator checks for a substring, so "ab" in "xaxb" is False.

Using brute force on long inputs. The brute force function is correct, but it tries every set of positions. For a long string with many matches, it can run for a very long time. It also makes one nested call for each letter, and Python stops a call chain after 1000 calls by default. This limit is the recursion limit. A string of 1200 letters goes past it before the function reaches any answer.

Traceback (most recent call last):
  ...
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

The first lines of the traceback are shortened here. The limit can be raised with sys.setrecursionlimit, but a deeper call chain still uses more memory. The table in num_distinct has no nested calls, so it works on long inputs. Use brute force only to check the table on short inputs, as the main block does.

Practice

Predict each answer on paper before you run anything. Each answer names the picks that make it.

Exercise 1. What is num_distinct("aab", "ab")?

Show the answer

It is 2. The two picks are positions 0 and 2, and positions 1 and 2. The letter b at position 2 is the only b, so it is used in both picks.

Exercise 2. What is num_distinct("bbb", "bb")?

Show the answer

It is 3. The pairs of positions that spell bb are 0 and 1, 0 and 2, and 1 and 2. Each pair is one pick, so there are three.

Exercise 3. What is num_distinct("ab", "ba")?

Show the answer

It is 0. The letter b appears after a in ab, so no pick can put a b before an a. Order matters, so ba cannot be spelled.

Exercise 4. What is num_distinct("xaxb", "ab"), and is ab a substring of xaxb?

Show the answer

The count is 1. The only pick uses position 1 for a and position 3 for b. The word ab is not a substring of xaxb, because the letters a and b are separated by an x in the string. "ab" in "xaxb" returns False.

Exercise 5. Explain in your own words why the one-row version must run j from high to low, using aaa and aa as the example.

Show the answer

When the inner loop runs downward, dp[j - 1] still holds the value from the row before the current letter of s. That is the value needed, because each letter can only be used once in a pick. When the loop runs upward, dp[j - 1] has already been updated for the current letter, so one a can be used for both letters of aa. For aaa and aa, the upward loop gives 6, and the downward loop gives the correct 3.

Summary

• A subsequence keeps the order of the letters but may skip letters, so ace is a subsequence of abcde and a substring search for it finds nothing.
• The table cell dp[i][j] counts the picks in the first i letters of s that spell the first j letters of t.
• The empty prefix of t has one pick in every prefix of s, so column 0 is 1 in every row.
• For a matching letter, the cell adds the skip count from the row above to the use count from the diagonal cell. For a non-matching letter, the cell only copies the row above.
• The one-row version works only when the inner loop runs from high to low, because each letter of s may be used once in a pick.
• Python integers keep every digit, so the table needs no overflow check, but the recursive brute force is limited to about 1000 nested calls.