Longest Common Subsequence — Solution & Editorial

Back to the Problem

Classic table: dp[i][j] extends by 1 on a character match, else takes the max of dropping one character from either string. One row of memory suffices.

Complexity: O(|A|·|B|)