Distinct subsequences and counting paths in strings

Why this matters

Many problems ask how many ways something can happen, not whether it can happen at all. A spell checker might ask how many ways a typed word can be produced by deleting letters from a longer text. A search tool might ask how many ways a short code appears in a log line, in order, with other letters in between. These are counting questions about strings, and a table lets you count them without listing every way.

This lesson counts subsequences. A subsequence is a string you get by deleting zero or more characters from another string, without changing the order of the rest. The lesson builds the table one letter at a time and derives the rule for each letter. The method is the same table idea from the earlier lessons in this module. The earlier lessons on counting paths in a grid use the same kind of rule, where each cell is a sum of cells before it.

Words you will need

• String: a sequence of characters. In C++ the examples use std::string_view for read-only text.
• Subsequence: a string made by deleting some characters from another string, keeping the order of the rest. The string ace is a subsequence of abcde, because you can delete b and d.
• Substring: a block of characters that is next to each other in the original string. bcd is a substring of abcde. ace is not a substring, because its letters are not next to each other.
• Way: one choice of positions in the long string. Two ways are different when they use a different set of positions, even if the letters spell the same word.
• Prefix: the first few characters of a string. The prefixes of bag are "", b, ba and bag.
• Table: a grid of numbers stored in a std::vector of std::vector. Here each cell holds a count.
• Base case: a value you write down directly for the smallest inputs.
• Empty string: a string with no characters, written "".

One example, counted by hand

Take the long string babgbag and the short string bag. Number the positions of the long string from 0 to 6:

position:  0 1 2 3 4 5 6
letter:    b a b g b a g

The letter b appears at positions 0, 2 and 4. The letter a appears at positions 1 and 5. The letter g appears at positions 3 and 6. A way is a choice of one position for b, then a later position for a, then a later position for g.

Count the ways by choosing the position of a first:

• a at position 1. The b must come before position 1, so it is at position 0. The g must come after position 1, so it is at position 3 or 6. That is 2 ways.
• a at position 5. The b must come before position 5, so it is at position 0, 2 or 4. The g must come after position 5, so it is at position 6. That is 3 ways.

The total is 2 + 3 = 5. The program later in this lesson prints the same answer.

Notice what the counting did. It did not list the strings. It added up the choices for each position of the last letter. The table does the same thing for every prefix at once.

The idea: a table over prefixes

Let s be the long string, with n characters, and t be the short string, with m characters. Build a table dp with n + 1 rows and m + 1 columns. The cell dp[i][j] answers this question:

How many ways can the first j characters of t appear as a subsequence of the first i characters of s?

The answer to the whole problem is the bottom-right cell, dp[n][m]. Here is the table for babgbag and bag, printed by the program later in this lesson. The first row and column are labelled '' for the empty string, and the row labels are the letters of s.

        ''   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

The bottom-right cell is 5, which matches the count made by hand above. Look at row 1, column b, which is 1. The first letter b of babgbag is the only way to match b. Look at row 3, column b, which is 2. The first three letters of the text are bab, and the b can be at position 0 or position 2.

The base cases

Two sets of base cases fill the table before the loop starts.

The first column has the empty string as the short string. Every prefix of s contains the empty string exactly once: choose no characters. So dp[i][0] is 1 for every row i, including row 0.

The first row has an empty prefix of s. A non-empty t cannot appear in an empty string, so dp[0][j] is 0 for every j at least 1.

These two base cases are the only cells that are not computed from other cells. The loop fills everything else.

The recurrence: deciding about the last letter

Now look at one cell dp[i][j] with i and j at least 1. The last letter of the long prefix is s[i - 1]. The last letter of the short prefix is t[j - 1]. There are two options for the last letter of s.

Option 1: do not use s[i - 1]. Any way to match the first j letters of t inside the first i - 1 letters of s is still a way inside the first i letters. Those ways are counted by dp[i - 1][j]. So this option always adds dp[i - 1][j].

Option 2: use s[i - 1] as the match for t[j - 1]. This works only when the two letters are equal. If s[i - 1] equals t[j - 1], the first j - 1 letters of t must be matched inside the first i - 1 letters of s. That count is dp[i - 1][j - 1]. So this option adds dp[i - 1][j - 1], but only on a letter match.

The two options do not overlap. A way either uses the last letter of s or it does not. So the cell is the sum of the two options:

dp[i][j] = dp[i - 1][j]                          always
         + dp[i - 1][j - 1]   if s[i - 1] == t[j - 1]

Check the rule on the cell in row a, column a from the table above. Row 2 is the prefix ba and column 2 is the prefix ba of t. The last letters are a and a, which are equal, so the second option applies. The first option gives dp[1][2], which is 0. The second option gives dp[1][1], which is 1, because the single letter b of s matches the b of t. The sum is 1. The only way to make ba from ba is to use both letters, so the answer 1 is right.

Walking a small table by hand

Take a slightly harder pair: the long string aab and the short string ab. Its table has four rows and three columns. The rows are the prefixes "", a, aa and aab. The columns are the prefixes "", a and ab. Here is the table, printed by a short Python check that uses the same rule:

[[1, 0, 0], [1, 1, 0], [1, 2, 0], [1, 2, 2]]

Each row of the list is one row of the table. Walk through three cells.

• Row 1 (a), column 1 (a). The letters match, so the cell adds the cell above, which is 0, and the cell diagonally above and to the left, which is dp[0][0], or 1. The result is 1. The only way to make a from a is that one letter.
• Row 2 (aa), column 1 (a). The letters match. The cell above is dp[1][1], which is 1, and the diagonal cell is dp[1][0], which is 1. The result is 2. The single a can come from position 0 or position 1.
• Row 3 (aab), column 2 (ab). The letters match, because the last letter is b. The cell above is dp[2][2], which is 0, because ab does not appear in aa. The diagonal cell is dp[2][1], which is 2, the count of a in aa. The result is 0 + 2 = 2. Those two ways are a at position 0 with b at position 2, and a at position 1 with b at position 2.

The cell in row 3, column 1 is also worth a look. The letter b does not match a, so it only copies the cell above, which is 2. The b in the text cannot be used for a, so the count of a stays at 2.

Why the rule counts every way once

The recurrence is correct because it sorts the ways into two groups without overlap and without gaps. Take any way to match the first j letters of t inside the first i letters of s. Look at the last position of that way.

If the way does not use position i - 1, it is a complete way inside the first i - 1 letters, which the cell above already counts. If the way does use position i - 1, that position is matched to t[j - 1], so s[i - 1] must equal t[j - 1]. The earlier letters of the way are then a way for t[0..j - 1) inside the first i - 1 letters, which the diagonal cell counts.

Each way falls into exactly one group, so adding the two counts does not count any way twice. Each way that exists is in one of the groups, so nothing is missing. This two-group argument is the proof you can write down for any counting table of this kind.

Program 1: counting subsequences

The program stores the table as std::vector<std::vector<std::uint64_t>>. It uses an unsigned 64-bit integer, because a count can grow very fast. The function takes two std::string_view arguments, so it does not copy either string.

#include <cstdint>
#include <iostream>
#include <string_view>
#include <vector>
 
// Counts the ways t appears as a subsequence of s.
// Two ways are different when they use different positions in s.
std::uint64_t countDistinctSubsequences(std::string_view s, std::string_view t) {
    const std::size_t n = s.size();
    const std::size_t m = t.size();
 
    // dp[i][j] is the number of ways the first j characters of t appear
    // inside the first i characters of s.
    std::vector<std::vector<std::uint64_t>> dp(n + 1, std::vector<std::uint64_t>(m + 1, 0));
 
    // Base: the empty string appears exactly once in any prefix of s,
    // by choosing no characters at all.
    for (std::size_t i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }
 
    for (std::size_t i = 1; i <= n; ++i) {
        for (std::size_t j = 1; j <= m; ++j) {
            // Option 1: do not use s[i - 1]. Every way from the shorter prefix still counts.
            dp[i][j] = dp[i - 1][j];
            // Option 2: if s[i - 1] equals t[j - 1], use it as the last matched character.
            // The first j - 1 characters of t must then fit inside the first i - 1 characters of s.
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] += dp[i - 1][j - 1];
            }
        }
    }
    return dp[n][m];
}
 
int main() {
    struct Case {
        std::string_view s;
        std::string_view t;
    };
    const std::vector<Case> cases = {
        {"rabbbit", "rabbit"},
        {"babgbag", "bag"},
        {"aaa", "a"},
        {"abc", "abcd"},
        {"abc", ""},
    };
    for (const auto& c : cases) {
        std::cout << '"' << c.s << "\" contains \"" << c.t << "\" as a subsequence in "
                  << countDistinctSubsequences(c.s, c.t) << " ways\n";
    }
 
    // Longer input: 60 a's and 30 a's. The count is C(60, 30).
    const std::string big_s(60, 'a');
    const std::string big_t(30, 'a');
    std::cout << "60 a's, 30 a's: " << countDistinctSubsequences(big_s, big_t) << '\n';
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -Wextra -o distinct_subsequences distinct_subsequences.cpp
./distinct_subsequences

The output is:

"rabbbit" contains "rabbit" as a subsequence in 3 ways
"babgbag" contains "bag" as a subsequence in 5 ways
"aaa" contains "a" as a subsequence in 3 ways
"abc" contains "abcd" as a subsequence in 0 ways
"abc" contains "" as a subsequence in 1 ways
60 a's, 30 a's: 118264581564861424

The first two lines match the hand counts. The "aaa" case has 3 ways, because the single a can be at position 0, 1 or 2. The "abc" case with the empty string has 1 way, the empty choice. The last number is C(60, 30), the number of ways to choose 30 positions out of 60. A Python check with math.comb(60, 30) gave the same value.

Second example: rabbbit and rabbit

The long string rabbbit has three b letters in a row. The short string rabbit has two. The r, the a and the final i and t each have only one possible position. The only freedom is which of the three b letters is left out. Leaving out the first, second or third b gives 3 ways, which matches the output.

This example shows why the table counts positions and not spellings. The word rabbit has one spelling, but there are three different pairs of positions for its two b letters out of the three in the text, so the count is 3.

Third example: aaa and a

The short string a appears once at each position of aaa, so the count is 3. The table handles this through the match rule. Column 1 counts the ways to make a from the first i letters. Each new a adds one more way, so the counts down column 1 are 1, 2 and 3.

A harder version uses a short string whose letters repeat. Count aa inside aaaa. The answer is C(4, 2) = 6, because any two of the four positions form a way. Exercise 2 in the Practice section checks this.

How to check an answer

A table is easy to get subtly wrong, so check it against a slow method on small inputs. The slow method lists every choice of positions and counts the ones that spell the short string. It is far too slow for long strings, but it is simple enough to trust.

import itertools
import random
 
def brute(s, t):
    count = 0
    for idx in itertools.combinations(range(len(s)), len(t)):
        if all(s[i] == t[k] for k, i in enumerate(idx)):
            count += 1
    return count
 
def table(s, t):
    n, m = len(s), len(t)
    d = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        d[i][0] = 1
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            d[i][j] = d[i - 1][j] + (d[i - 1][j - 1] if s[i - 1] == t[j - 1] else 0)
    return d[n][m]
 
random.seed(3)
bad = 0
for _ in range(3000):
    s = "".join(random.choice("ab") for _ in range(random.randint(0, 9)))
    t = "".join(random.choice("ab") for _ in range(random.randint(0, 4)))
    if brute(s, t) != table(s, t):
        bad += 1
print("mismatches", bad)

Run with python3 check.py. The output is:

mismatches 0

The random test used texts of up to 9 letters and short strings of up to 4 letters over the letters a and b. The itertools.combinations call picks every set of positions in order. The brute force and the table agreed on all 3000 cases. A test like this catches most slips in the base cases and the match rule, because small random inputs hit both.

Common mistakes

Adding the match count only when letters match. Some beginners write the rule as "the letters match, so add the diagonal cell, otherwise use zero". That throws away every way that skips the last letter of s. The bug below is a variant of Program 1 with dp[i][j] set to 0 when the letters differ.

zeroOnMismatch(rabbbit, rabbit) = 2
zeroOnMismatch(babgbag, bag) = 1

The correct answers are 3 and 5. The fix is to copy dp[i - 1][j] first and add to it only when the letters match.

Confusing a subsequence with a substring. The string ab is a subsequence of acb, because you can delete c. It is not a substring of acb, because a and b are not next to each other. If the problem asks for contiguous blocks, a different table is needed. This lesson counts subsequences only.

Overflow in the count. The number of ways can grow very quickly. The count for 60 a letters and 30 a letters fits in 64 bits, but the count for 100 letters and 50 letters does not. The program does not stop with an error. An unsigned integer wraps around, so the output is a wrong number that looks normal:

100 a's, 50 a's (unsigned 64-bit) = 1184508333840160104

The true value is 100891344545564193334812497256, which Python's math.comb(100, 50) prints. The printed value is that true value reduced modulo 2 to the power 64. When a problem asks for an answer modulo a number such as 1000000007, take the remainder at every addition, as the exercise below shows. Without that, the count can wrap around silently.

Practice

Exercise 1. Count the ways ab appears as a subsequence of acbxab. List the positions you use.

Show the answer

There are 3 ways. The a at position 0 can pair with the b at position 2 or the b at position 5. The a at position 4 can pair with the b at position 5. Calling countDistinctSubsequences on these inputs returns 3.

Exercise 2. Count the ways aa appears as a subsequence of aaaa. Use the formula for choosing 2 items out of 4.

Show the answer

There are 6 ways. The count is C(4, 2) = 4 * 3 / 2 = 6, because any two of the four positions give one way. Calling countDistinctSubsequences on these inputs returns 6.

Exercise 3. Is abc a subsequence of cba? Give the count.

Show the answer

No. The count is 0. In cba the letter a comes after b, so no order of positions can spell abc. Calling countDistinctSubsequences on these inputs returns 0.

Exercise 4. Count the ways ab appears in aab. Write the last row of the table, from dp[3][0] to dp[3][2].

Show the answer

There are 2 ways: a at position 0 with b at position 2, and a at position 1 with b at position 2. The last row of the table is 1 2 2. The 1 in column 0 is the empty-string base case. The 2 in column 1 says the letter a appears in aab in 2 ways. The 2 in column 2 is the answer.

Exercise 5. Count the ways 50 a letters appear in 100 a letters, and report the answer modulo 1000000007. Change the table so that the value never grows past that number.

Show the answer

Keep the same loops and base cases. Inside the match branch, replace the addition with dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % 1000000007. The result is 538992043. The Python value math.comb(100, 50) % 1000000007 gives the same number.

Summary

• A table cell dp[i][j] counts the ways the first j letters of the short string appear in the first i letters of the long string.
• The first column is 1 everywhere, because the empty string appears once. The first row is 0 after column 0, because a non-empty string cannot appear in nothing.
• Each cell adds the count from the row above, which means "do not use the last letter". It adds the diagonal cell too, when the last letters match.
• Use an unsigned 64-bit type only when the count is known to fit, and reduce modulo a number when the problem asks for one.
• The same table can be shrunk to one row. That idea is covered in the lesson on longest common substring and rolling rows.