Tri's external memory

Lesson 5 Longest Common Subsequence (LCS)

3 min read

Problem

Given two strings:

A = ABCDE
B = ACE

Find the length of the longest subsequence common to both strings.

Result:

LCS = ACE
Length = 3

Subsequence vs Substring

Subsequence

Characters remain in order.

Characters may be skipped.

Example:

ABCDE

Valid subsequences:

ACE
ABD
AE
A

Invalid:

AEC

because the order changed.

Recursive Thinking

Define:

lcs(i, j)

Meaning:

Length of the LCS between:
 
A[i..end]
B[j..end]

Example:

lcs(2,1)

For:

A = ABCDE
B = ACE

means:

LCS(
    "CDE",
    "CE"
)

Result:

2

because:

CE

is common.

State Definition

State:

dp[i][j]

Meaning:

Length of the LCS between:
 
A[i..end]
B[j..end]

This is called the suffix formulation.

Why Two Dimensions?

The future depends on:

position in A
position in B

A single parameter is insufficient.

Therefore:

State = (i, j)

Recurrence

Match

If:

A[i] == B[j]

Then:

dp[i][j]
=
1 + dp[i+1][j+1]

Reason:

The matching character belongs to the LCS.

Move diagonally.

Mismatch

If:

A[i] != B[j]

Then:

dp[i][j]
=
max(
    dp[i+1][j],
    dp[i][j+1]
)

Meaning:

Skip A[i]
or
Skip B[j]

Choose the better result.

Golden Rule

Match
→ 1 + diagonal
 
Mismatch
→ max(down, right)

Never mix the two cases.

The +1 reward is only applied when characters match.

Base Cases

When:

i == len(A)

or

j == len(B)

One string is exhausted.

Therefore:

dp[i][j] = 0

because no common subsequence remains.

Table Interpretation

Example:

A = ABC
B = AC

State:

dp[2][1]

means:

LCS(
    "C",
    "C"
)

Answer:

1

because:

"C"

matches.

Example Computation

A = ABC
B = AC

dp[2][1]

C == C
 
dp[2][1]
=
1 + dp[3][2]
=
1

dp[1][1]

B != C
 
dp[1][1]
=
max(
    dp[2][1],
    dp[1][2]
)
=
max(1,0)
=
1

dp[0][0]

A == A
 
dp[0][0]
=
1 + dp[1][1]
=
2

Result:

LCS = AC
Length = 2

Geometry of the Table

Each state depends on:

right
down
diagonal

Visualized as:

          j
      +---+---+
i     | * | R |
      +---+---+
i+1   | D | X |
      +---+---+

Where:

R = dp[i][j+1]
D = dp[i+1][j]
X = dp[i+1][j+1]

Dependencies:

Match
→ diagonal
 
Mismatch
→ right and down

Recursion Tree vs DP Table

Recursive View

Think about one function call:

lcs(i,j)

which generates:

lcs(i+1,j)
lcs(i,j+1)
lcs(i+1,j+1)

Only visited states are visible.

DP Table View

All possible states are visible:

(0,0)
(0,1)
(0,2)
(1,0)
(1,1)
...

Every cell corresponds to a recursive call.

Important realization:

dp[i][j]

is simply:

lcs(i,j)

written down.

The DP table is the recursion tree flattened into a grid.

Personal Observation

Initially it is natural to imagine:

i moving through string A
j moving through string B

as two pointers.

The difficult part of 2D DP is realizing that:

all combinations of (i,j)

exist simultaneously.

This creates a grid of hidden states that must be filled.

This is normal.

The table is not introducing new information.

It merely exposes all recursive states at once.

Important Mental Model

Recursive function
      ↓
All possible function calls
      ↓
Organize calls by parameters
      ↓
DP table

For LCS:

lcs(i,j)

becomes:

dp[i][j]

The table is simply a cache of recursive states.

New DP Pattern

Previous lessons:

Fibonacci
Climbing Stairs
House Robber
Coin Change

mostly used:

State = one variable

LCS introduces:

State = (i, j)

representing positions in two sequences simultaneously.

This pattern reappears in:

Edit Distance
Diff tools
Git merge algorithms
DNA sequence alignment
Spell checking

Understanding LCS is the foundation for all of them.

Graph View

Backlinks