Longest Common Subsequence

When git diff lines up two versions of a file, or a biology tool aligns two strands of DNA, it's solving the same underlying question: what's the longest run of items that appears in both sequences, in the same order, even if other items are sprinkled between them? That longest run is the longest common subsequence (LCS). A subsequence keeps the relative order of characters but does not require them to be next to each other — "ace" is a subsequence of "abcde", but "aec" is not. Your job is to return the length of the longest subsequence common to two strings.

Signature

// Returns the LENGTH of the longest common subsequence of a and b.
function longestCommonSubsequence(a: string, b: string): number;

Examples

longestCommonSubsequence('abcde', 'ace'); // → 3   ("ace" appears in both, in order)
longestCommonSubsequence('abcabba', 'cbabac'); // → 4   ("baba" appears in both, in order)
longestCommonSubsequence('GAC', 'AGCAT'); // → 2   ("GA", "AC", and "GC" are all length 2)

longestCommonSubsequence('abc', 'def'); // → 0   (no character in common)
longestCommonSubsequence('abc', 'cba'); // → 1   (order matters: only one char lines up)
longestCommonSubsequence('', 'anything'); // → 0   (empty string shares nothing)

Notes

• Subsequence, not substring. The matched characters do not have to be contiguous. "ae" is a valid common subsequence of "abcde" even though a and e are far apart. (A substring would require them adjacent — that is a different, stricter problem.)
• Order is preserved. You may delete characters from either string, but you may not reorder them. That is why 'abc' and 'cba' share a subsequence of length 1, not 3.
• Return the length, not the string. A final return dp[m][n] is the goal. Reconstructing the actual subsequence is a follow-up, covered in the solution's "Going further".
• Empty input → 0. If either string is empty, the answer is 0; there is nothing to share.
• Case-sensitive. 'A' and 'a' are different characters and do not match. Don't lowercase the inputs.
• Inputs are plain strings. Assume both arguments are strings (possibly empty). You don't need to handle null, numbers, or other types.