AlgoPlus//dynamic programming / lcs

Longest Common Subsequence

Align two strings on a grid; matches grow the answer along the diagonal.

Phase

Done

X · Y

—

LCS

—

String X (letters only, max 12)

String Y (letters only, max 12)

Legend

Current cell

Derived from

Traceback / kept letter

AI Tutor Workspace

—

In a nutshell

The longest common subsequence is the longest run of letters that appears in both strings in the same order, though not necessarily next to each other. A grid compares every prefix of one string against every prefix of the other; a matching letter grows the run diagonally, and the bottom-right cell holds the final length.

Ready

Press play to begin the cinematic walkthrough.

Line the two strings up on a grid. A matching letter extends the best diagonal run; a mismatch just inherits the better neighbour. The bottom-right corner holds the answer.

Key terms

Go deeper in the lesson

Read the full theory, intuition & complexity for Longest Common Subsequence.