26. Longest Common KB Snippet

Problem

Fin's knowledge base ingestion pipeline flags likely duplicate or near-duplicate articles before they reach the retrieval index, since duplicate KB content degrades retrieval quality and reranking signal. One heuristic: tokenize each article and measure the length of the longest common (not necessarily contiguous) subsequence of shared tokens between the two token lists. A high overlap suggests the two articles cover the same guidance and should be flagged for review or merging.

Given two token lists a and b, return the length of their longest common subsequence — the longest sequence of tokens that appears, in order but not necessarily contiguously, in both lists.

Source: src/26_longest_common_kb_snippet.py

def lcs_length(a: list[str], b: list[str]) -> int: ...

lcs_length(["reset", "your", "password", "now"], ["how", "to", "reset", "password"])
# -> 2   ("reset", "password" appear in order in both)

lcs_length(["a", "b", "c"], ["a", "b", "c"])
# -> 3

Step-by-Step Approach

1. Let n = len(a), m = len(b). Build a (n+1) x (m+1) DP table dp, where dp[i][j] is the LCS length of the prefixes a[:i] and b[:j].
2. Initialize row 0 and column 0 to all zeros — an empty prefix has no common subsequence with anything.
3. Fill the table left-to-right, top-to-bottom for i from 1 to n and j from 1 to m.
4. If a[i-1] == b[j-1] (the current tokens match), the LCS can extend the best subsequence found without either of these two tokens: set dp[i][j] = dp[i-1][j-1] + 1.
5. Otherwise, the current tokens can't both be part of the LCS together, so take the best of dropping one or the other: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
6. The answer is dp[n][m], the LCS length of the full lists.

The key insight is that the LCS of two prefixes only depends on the LCS of smaller prefixes, so a bottom-up table avoids the exponential blowup of trying every subsequence directly. Time and space are both O(n * m).

Reference solution

def lcs_length(a: list[str], b: list[str]) -> int:
    # bottom-up DP table, dp[i][j] = LCS length of a[:i] and b[:j], O(len(a)*len(b)) time/space
    n, m = len(a), len(b)
    # fresh list per row, avoids aliasing bug
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    # 1-indexed: dp[i] aligns to a[i-1]
    for i in range(1, n + 1):
        # dp[j] aligns to b[j-1]
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # drop from a or b, keep the better
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Key Functions & Tricks

• [[0] * (m + 1) for _ in range(n + 1)] — builds independent per-row lists, avoiding the aliasing bug of [[0]*(m+1)]*(n+1).
• range(1, n + 1) — 1-indexes the DP table while a/b stay 0-indexed.
• max(dp[i - 1][j], dp[i][j - 1]) — picks the best LCS length after dropping one token.

How to Recognize This Pattern