Longest Common Subsequence

Signal

Two sequences being compared position by position, where the answer for a pair of prefixes depends on the answer for slightly shorter prefixes of both — that "state = (index into A, index into B)" shape is what separates this family from 1-D DP.

Approach

Build a table dp[i][j] = the LCS length of s1[:i] and s2[:j]. If the characters at s1[i-1] and s2[j-1] match, they can both extend a common subsequence, so dp[i][j] = dp[i-1][j-1] + 1. If they don't match, the best you can do is whichever of "drop the last char of s1" or "drop the last char of s2" gives the longer subsequence already computed.

Skeleton

dp[0][*] = dp[*][0] = 0
for i in 1..len(s1):
    for j in 1..len(s2):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[len(s1)][len(s2)]

Solution

def longest_common_subsequence(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    return prev[n]

Complexity

O(m · n) time — one cell per pair of prefixes. O(n) space by keeping only the previous row instead of the full 2-D table.

Pitfalls

• Confusing this with longest common substring — that variant requires contiguity and resets to 0 on a mismatch instead of taking a max from either direction.
• Off-by-one between the string index (i-1) and the DP index (i) — the DP table is deliberately 1-indexed with an extra empty-prefix row/column so dp[0][*] and dp[*][0] can cleanly mean "one string is empty."
• Reconstructing the actual subsequence (not just its length) requires walking back through the table from dp[m][n], which needs the full 2-D table kept around — the space-optimized rolling-row version can't do this.