ZERO / HERO
What two texts still agree on

Longest Common Subsequence

The analogy

Line up two words in a grid. Walk it cell by cell: if the letters match, you extend the agreement you already had diagonally behind you. If they do not, you keep the better of ignoring one letter from either word. The bottom-right corner is your answer.

Visualizer

Where two strings agree

step 1 / 8
BDCABA
0000000
A
B
C
B
D
A
B

Longest common subsequence of "ABCBDAB" and "BDCABA". Subsequence means in order but NOT necessarily adjacent.dp[i][j] = LCS of first i of A, first j of B

def lcs_length(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1        # diagonal
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

def lcs_string(a, b):
    dp = lcs_table(a, b)
    i, j, out = len(a), len(b), []
    while i and j:                     # walk back from corner
        if a[i-1] == b[j-1]:
            out.append(a[i-1]); i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(out))

# longest common SUBSTRING differs by one line:
#   else: dp[i][j] = 0          # contiguity broken
Check yourself

LCS vs longest common substring — what changes in the recurrence?