Dynamic Programming • 2D Arrays

Longest Common Subsequence

Find the length of the longest subsequence common to two strings. A foundational DP problem.

Overview

LCS asks you to find the longest common sequence of characters that appear in the same relative order in both strings, but not necessarily contiguously.

The Logic

If characters match, the sequence length increases by 1 relative to the sequences before both characters. If not, the sequence is the max of ignoring the character from string A or string B.

The Grid

We build an `(M+1) x (N+1)` grid where `dp[i][j]` represents the LCS of prefixes `text1[0..i-1]` and `text2[0..j-1]`.

Retrieving the String

You can trace back from `dp[M][N]` to find the actual string. If chars matched, move diagonal-up-left. Otherwise, move to the max of Top or Left.

T1 \ T2	""	a	b	c	d	e
""	0	0	0	0	0	0
a	0	0	0	0	0	0
c	0	0	0	0	0	0
e	0	0	0	0	0	0

Code Tracker

:::

1for (let i = 1; i <= m; i++) {

2 for (let j = 1; j <= n; j++) {

3 if (text1[i-1] === text2[j-1]) {

4 dp[i][j] = 1 + dp[i-1][j-1];

5 } else {

6 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);

7 }

8 }

9}