Longest Common Subsequence

Statement

Given two strings a and b, return the length of their longest common subsequence. A subsequence is a sequence derived from the original by deleting some (or no) characters without changing the order. If no common subsequence exists, return 0.

Examples

a = "abcde", b = "ace"
→ 3     ("ace" appears in both)

a = "abc", b = "abc"
→ 3     (identical strings)

a = "abc", b = "def"
→ 0     (no shared characters)

a = "bsbininm", b = "jmjkbkjkv"
→ 1     (just "b" or "j")

Constraints

• 1 ≤ len(a), len(b) ≤ 1000
• Both strings consist of lowercase English characters.

What this problem is really testing

The canonical 2D string DP. Whether you can identify the state as "the LCS of the first i characters of A and the first j characters of B", write the transition (depends on whether the new characters match), and roll the table into O(min(n, m)) memory. Edit distance, shortest common supersequence, and most string-alignment problems use the same shape.