← All problems

String dynamic programming · recursion + memoization

Count how many times A appears as a subsequence in B

Input: a target string A and a source string B. Output: the number of distinct choices of positions in B that spell A in order. Characters may be skipped, but their order cannot change. Two choices count separately when they use different B indices, even if they spell the same text. The empty A has one way to match any B: choose no positions.

A = “AB”B = “AAB”Choose B indices (0, 2) or (1, 2)Answer = 2

The recursive question

How many ways can this A suffix fit in this B suffix?

solve(i, j) counts the ways to form A[i:] from B[j:]. At each B character, decide whether it becomes the next A character or is skipped. Memoization saves the count for each index pair.

A exhausted → 1

All target characters were selected, so this branch is one complete match.

B exhausted → 0

If A still has characters, this branch cannot complete the match.

Match → add

If the letters match, count both use and skip choices. Otherwise, skip B’s character.

A[i] == B[j] → solve(i+1, j+1) + solve(i, j+1)

There are at most (m + 1)(n + 1) memo states, each doing constant-count arithmetic: O(mn) time and O(mn) space, excluding the bit cost of very large integers. Plain recursion can revisit the same states exponentially many times.

Interactive call trace

Watch use and skip add up

The table stores how many completions each pair of suffixes has.

Memoized suffix states
Current character / stateMatching charactersSaved memo value

Target A · indices

Source B · indices

Memo table · row i, column j

Active recursive call stack

Python reference

From recursion to memoization

The animation follows the memoized version: match the next letter using B’s current position, or skip that position and try later ones.

from functools import cache

def count_subsequences(a: str, b: str) -> int:
    @cache
    def solve(i: int, j: int) -> int:
        if i == len(a):
            return 1
        if j == len(b):
            return 0

        if a[i] == b[j]:
            use = solve(i + 1, j + 1)
            skip = solve(i, j + 1)
            return use + skip
        return solve(i, j + 1)

    return solve(0, 0)

print(count_subsequences("AB", "AAB"))  # 2

Count A as a Subsequence in B · Algorithm Atlas