String dynamic programming · recursion + memoization

Print a longest common subsequence

Input: two strings A and B. Output: one longest string that appears in both in the same left-to-right order. You may skip characters, but you cannot rearrange them; the characters need not be adjacent. If several longest answers exist, any one is valid. An empty string is valid when nothing matches.

A = “ABC”B = “AC”One answer = “AC”

The recursive question

What is the best answer from these two suffixes?

solve(i, j) returns a longest common subsequence of A[i:] and B[j:]. The returned string itself lets us print the answer. Memoization saves each pair of indices after its first solution.

Base case

If either suffix is empty, return the empty string.

Matching letters

Keep that letter once and advance both indices.

Different letters

Try skipping A’s letter or B’s letter, then return the longer result.

solve(i, j) depends only on i and j. There are at most (m + 1)(n + 1) states. Returning strings copies up to min(m, n) characters per state, so this direct memoized version takes O(mn · min(m, n)) time and space in the worst case.

Interactive call trace

Follow the recursion and memo

Move one event at a time. The highlighted cell is the current pair of suffix indices.

Memoized suffix states

Current character / stateMatching charactersSaved memo value

A · indices

B · indices

Memo table · row i, column j

Active recursive call stack

Python reference

From recursion to memoization

Both versions return a string, not just its length. The animation follows the memoized version. On a tie, it chooses the branch that skips A’s current character.

from functools import cache

def print_lcs(a: str, b: str) -> str:
    @cache
    def solve(i: int, j: int) -> str:
        if i == len(a) or j == len(b):
            return ""
        if a[i] == b[j]:
            return a[i] + solve(i + 1, j + 1)

        skip_a = solve(i + 1, j)
        skip_b = solve(i, j + 1)
        return skip_a if len(skip_a) >= len(skip_b) else skip_b

    return solve(0, 0)

print(print_lcs("ABC", "AC"))  # AC

def print_lcs_recursive(a: str, b: str) -> str:
    def solve(i: int, j: int) -> str:
        if i == len(a) or j == len(b):
            return ""
        if a[i] == b[j]:
            return a[i] + solve(i + 1, j + 1)

        skip_a = solve(i + 1, j)
        skip_b = solve(i, j + 1)
        return skip_a if len(skip_a) >= len(skip_b) else skip_b

    return solve(0, 0)

Plain recursion recomputes overlapping states and can take exponential time.