3. Diff Two Draft Responses with Longest Common Subsequence

Problem

When comparing two draft responses (e.g. a base model's answer versus a fine-tuned variant's answer, for a side-by-side eval), it's useful to see which words the two drafts share in common, in the order they occur, so a reviewer can see what changed.

This is the longest common subsequence (LCS) problem applied at word granularity instead of character granularity.

Source: src/3_diff_drafts_lcs.py

def longest_common_subsequence(draft_a: str, draft_b: str) -> list[str]:
    ...

Examples:
>>> longest_common_subsequence("the cat sat on the mat", "the cat sat on a mat")
['the', 'cat', 'sat', 'on', 'mat']

>>> longest_common_subsequence("a b c", "x y z")
[]

Step-by-Step Approach

1. Split both drafts on whitespace into word lists — the problem is now classic LCS over two sequences of tokens, not characters.
2. Build a DP table dp[i][j] = length of the LCS of a[i:] and b[j:], filled from the bottom-right corner backward: if a[i] == b[j], dp[i][j] = 1 + dp[i+1][j+1]; otherwise dp[i][j] = max(dp[i+1][j], dp[i][j+1]).
3. Recognize that the table alone only gives you the LCS *length* — to return the actual words, you need a second pass that reconstructs a path through the table.
4. Walk forward from (0, 0): whenever a[i] == b[j], that word is part of the LCS, append it and advance both i and j; otherwise step toward whichever neighbor cell (dp[i+1][j] or dp[i][j+1]) has the larger value.
5. Stop the walk once either index reaches the end of its list, and return the collected words in order.

The key insight is that the DP table only encodes lengths — recovering the actual subsequence needs a second, direct pass over the same table rather than storing backpointers, since the greater-neighbor rule at each cell already tells you which way the optimal path went.

Reference solution

def longest_common_subsequence(draft_a: str, draft_b: str) -> list[str]:
    a = draft_a.split()
    b = draft_b.split()
    n, m = len(a), len(b)
    # dp[i][j] = length of LCS of a[i:] and b[j:]; classic O(n*m) table
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            if a[i] == b[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])

    # walk the table forward to reconstruct one actual LCS, not just its length
    i = j = 0
    out = []
    while i < n and j < m:
        if a[i] == b[j]:
            out.append(a[i])
            i += 1
            j += 1
        elif dp[i + 1][j] >= dp[i][j + 1]:
            i += 1
        else:
            j += 1
    return out

Key Functions & Tricks

• draft.split() — tokenizes to word granularity so the LCS runs over words, not characters
• dp[i][j] = 1 + dp[i+1][j+1] — extends the LCS length by one when the current words match
• dp[i][j] = max(dp[i+1][j], dp[i][j+1]) — carries forward the better of skipping a word from either sequence
• backward-filled 2D table — O(n*m) time and space, filled from the end so forward reconstruction is possible
• forward reconstruction walk — reads the same table a second time to recover the actual sequence, not just its length

How to Recognize This Pattern