Longest Common Subsequence

Background

Longest Common Subsequence (LCS) is the heart of ROUGE-L and many sequence-alignment problems. Given two strings, find the longest sequence (not necessarily contiguous) of characters appearing in both, in order. Classic dynamic-programming exercise; $O(|a| \cdot |b|)$ time and space for the canonical version.

Problem statement

Implement lcs_length(a, b) returning the length of the LCS via:

$$\text{dp}[i][j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ \text{dp}[i-1][j-1] + 1 & \text{if } a_{i-1} = b_{j-1} \\ \max(\text{dp}[i-1][j],\ \text{dp}[i][j-1]) & \text{otherwise} \end{cases}$$

Return dp[len(a)][len(b)].

Input

• a — str.
• b — str.

Output

Returns int >= 0, the LCS length.

Examples

Example 1 — classic worked example

Input:  a="ABCBDAB", b="BDCAB"
Output: 4

Explanation: LCS is BDAB (or BCAB).

Example 2 — identical strings

Input:  a="abcd", b="abcd"
Output: 4

Example 3 — disjoint alphabets

Input:  a="abc", b="xyz"
Output: 0

Example 4 — subsequence, not substring

Input:  a="axbycz", b="abc"
Output: 3

Constraints

• Empty inputs → 0.
• $O(|a| \cdot |b|)$ time and space is acceptable; space can be reduced to $O(\min(|a|, |b|))$ as an optimisation.

Notes

• ROUGE-L. F-measure built on LCS — captures the longest aligned spans between prediction and reference without needing $n$-gram counting.
• Edit distance vs LCS. Levenshtein = $|a| + |b| - 2 \cdot \text{LCS}(a, b)$ when the only allowed edits are insert/delete (no substitution). Both are sister DPs.