Longest Common Subsequence

Memoized recursion — branch only when characters differ

At positions i and j, matching characters belong together: count one and advance both positions. When they differ, skip either text1[i] or text2[j] and keep the better result.

A raw recursion repeats the same pair of positions. Dynamic programming (DP) stores answers to overlapping smaller problems; memoization is the top-down form that caches each (i, j) answer after computing it once.

from functools import cache
 
 
def longest_common_subsequence(text1: str, text2: str) -> int:
    @cache
    def solve(i: int, j: int) -> int:
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + solve(i + 1, j + 1)
        return max(solve(i + 1, j), solve(i, j + 1))
 
    return solve(0, 0)

The recurrence examines the full choice space without recomputing a state. It also makes the correctness argument visible: a matching pair advances both strings, while a mismatch forces at least one current character to be absent from any chosen answer.

Time O(mn) because there are at most m · n position pairs. Space O(mn) for the cache, plus a recursion stack of at most m + n calls.

One-row LCS DP — roll the table forward

The bottom-up LCS DP usually uses a grid where each cell stores the answer for two prefixes. Only the previous row is needed, so one row is enough if you preserve the old diagonal before overwriting it.

def longest_common_subsequence(text1: str, text2: str) -> int:
    if len(text2) > len(text1):
        text1, text2 = text2, text1
 
    dp = [0] * (len(text2) + 1)
 
    for char1 in text1:
        diagonal = 0
        for j, char2 in enumerate(text2, start=1):
            above = dp[j]
            if char1 == char2:
                dp[j] = diagonal + 1
            else:
                dp[j] = max(dp[j], dp[j - 1])
            diagonal = above
 
    return dp[-1]

Before an update, dp[j] is the cell above and diagonal is the previous row's dp[j - 1]. After an update, dp[j - 1] is the cell to the left. Those are exactly the three neighbors in the two-dimensional recurrence.

Time O(mn) because every pair of character positions is processed once. Space O(min(m, n)) because the shorter string controls the row width.