---
title: "longest common subsequence"
type: concept
source: https://www.jemoka.com/posts/kbhlongest_common_subsequence/
confidence: high
status: active
---

BDFH is a subsequence of ABCDEFGH. Given two lists, what&rsquo;s the longest common subsequence?
optimal substructure We consider sub problems&rsquo; of finding LCS of prefixes \(C[i,j]\). Casework:
C[i,j] = &hellip;
for A[i] = B[j], then C[i,j] = C[i-1, j-1] + 1 for A[i] != B[j] = max(C[i,j-1], C[i-1,j]) if i=0 or j=0, then 0 Filling this table is \(O\qty(nm)\), and backtracing takes \(O\qty(n+m)\).
