DSA Distinct Subsequences
Counting distinct subsequences means counting the ways one string hides inside another in order. A prefix table counts the ways without listing them.
The problem
Counting distinct subsequences means counting the ways one string hides inside another in order. The short string is the pattern. The long string is the text, and its characters get picked or skipped.
Two ways are different when they pick different positions. The picked letters may look identical. The positions decide.
The cases used in this article
cases = [
("rabbbit", "rabbit", 3),
("babgbag", "bag", 5),
("abc", "d", 0),
("aaaa", "aa", 6),
]
for text, pattern, expected in cases:
print(repr(pattern), "in", repr(text), "->", expected)The last row counts position pairs. Four copies of the letter a hold six ordered pairs of positions. Each pair spells the pattern aa.
Intuition: multiplying choices overcounts
The first idea counts choices letter by letter. It counts where the first pattern letter can sit. It then counts where the second can sit, and multiplies.
Multiplication ignores order between the picks. It counts pairs where the second letter sits before the first. Those pairs spell nothing.
The product rule against aaaa and aa
text = "aaaa"
choices_first = 4
choices_second = 4
print("naive product:", choices_first * choices_second)
print("ordered pairs of positions:", 4 * 3 // 2)
print("note: only pairs in rising order spell 'aa'")The product says sixteen. The true count is six. Every counted way must respect the rising order of positions, and the naive product never checks it.
Brute force: list every subset of positions
A pick is a subset of the text positions. The subset keeps its positions in rising order. The letters at those positions must spell the pattern exactly.
A text of length m has 2 to the power m subsets. The brute force builds each picked string and compares it with the pattern.
The brute force, counted
def count_brute(text, pattern):
count = 0
tested = 0
for mask in range(2 ** len(text)):
picked = "".join(text[i] for i in range(len(text)) if mask >> i & 1)
tested += 1
if picked == pattern:
count += 1
return count, tested
for text, pattern in [("rabbbit", "rabbit"), ("aaaa", "aa")]:
count, tested = count_brute(text, pattern)
print(repr(pattern), "in", repr(text), "->", count, "subsets tested:", tested)Seven text letters already force 128 subsets. Most subsets spell something else entirely. The brute force pays for all of them to count a handful.
The optimal solution: a prefix table that adds skip and use
The state dp[i][j] counts the ways to spell the first j pattern characters from the first i text characters. An empty pattern has exactly one way, the empty pick, so the first column is all ones.
Each new text character may be skipped, which copies the count from above. A matching character may also be used, which adds the diagonal count. A non-match adds nothing.
The prefix table on every case
def count_ways(text, pattern):
m, n = len(text), len(pattern)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j]
if text[i - 1] == pattern[j - 1]:
dp[i][j] += dp[i - 1][j - 1]
return dp[m][n]
cases = [
("rabbbit", "rabbit", 3),
("babgbag", "bag", 5),
("abc", "d", 0),
("aaaa", "aa", 6),
]
for text, pattern, expected in cases:
result = count_ways(text, pattern)
print(repr(pattern), "in", repr(text), "->", result, "expected:", expected, "match:", result == expected)All four cases pass. The zero row works because a missing letter never adds a diagonal count. The count stays zero from the first cell to the last.
Walkthrough: spelling ab inside aab
The walkthrough uses a short text with a repeated first letter. The text is aab. The pattern is ab, and it hides two ways, one per copy of a.
The table gains one row per text character. The first column stays at one throughout. Each row shows the counts after that character joins.
The table after each text character
text, pattern = "aab", "ab"
m, n = len(text), len(pattern)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
print("before any character:", dp[0])
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j]
if text[i - 1] == pattern[j - 1]:
dp[i][j] += dp[i - 1][j - 1]
print("after text character", i, repr(text[i - 1]), "row:", dp[i])
print("answer:", dp[m][n])The second row lifts the count for the pattern a to two, one per copy of the letter. The third row then lifts the ab count straight to two, because the letter b can pair with either earlier a. The bottom right cell is read off as the answer.
Complexity
The table fills one cell per pair of prefixes, so its time is O(m times n) for text length m and pattern length n. The brute force tests 2 to the power m subsets instead.
The table stores every cell, so its space is O(m times n). The count itself can grow fast, and Python integers hold it exactly at any size.
Subsets against cells at three sizes
for m in [7, 10, 20]:
print("text length", m, "- brute subsets:", 2 ** m, " table cells for pattern length 4:", m * 4)Counts beat clocks here as well. At text length 20 the subset count passes one million. The table for a short pattern stays in double figures.
Edge cases and pitfalls
An empty pattern counts exactly once for every text. Picking nothing spells it. A table that starts its first column at zero destroys that base case and zeroes every count.
A pattern longer than the text counts zero. Some prefix of the pattern can never be completed. The table reaches that answer without any special check.
Edge cases, run
def count_ways(text, pattern):
m, n = len(text), len(pattern)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = dp[i - 1][j]
if text[i - 1] == pattern[j - 1]:
dp[i][j] += dp[i - 1][j - 1]
return dp[m][n]
print("empty pattern:", count_ways("abc", ""))
print("both empty:", count_ways("", ""))
print("pattern longer than text:", count_ways("ab", "abc"))
print("missing letter:", count_ways("abc", "d"))
print("all same letter:", count_ways("aaaa", "aa"))
print("pattern equals text:", count_ways("abc", "abc"))The pattern-equals-text row counts one. Only the full pick works. Any skipped character leaves the spelling short.
Exercise
A text character matches the next needed pattern character. What does the cell add?