Longest Common Subsequence
Align two strings with a DP table.
Longest Common Subsequence is a free Coding Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What a Subsequence Is
A subsequence keeps characters in order but may skip some. From 'abcde' you can take 'ace', but never 'aec'.
The LCS Goal
Given two strings, the longest common subsequence is the longest sequence that appears in both, in the same relative order.
Move to a Grid
Compare prefixes of the two strings. A 2D table over their lengths turns this into a familiar grid DP.
Define the State
Let dp[i][j] be the LCS length of the first i characters of A and the first j characters of B.
When Characters Match
If A[i-1] equals B[j-1], that shared letter extends the LCS. You add one to the diagonal value dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1When They Differ
If the letters differ, drop one character from either string and keep the better result. You take the max of two neighbors.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])The Base Case
An empty prefix shares nothing, so the LCS length is zero. Row 0 and column 0 stay all zeros.
dp = [[0] * (m+1) for _ in range(n+1)]One Extra Row and Column
Sizing the table with n+1 by m+1 gives a free zero border. That removes annoying bounds checks at the edges.
Fill It Up
Loop i and j from 1 upward. Each cell only needs values above, left, and diagonal, which are already computed.
for i in range(1, n+1):
for j in range(1, m+1):
...Read the Length
The full LCS length sits in the corner. The answer is dp[n][m] once every cell is filled.
length = dp[n][m]Complexity
You touch every cell once, so the work is O(n times m) time and memory. That comfortably handles strings up to a few thousand long.
Quick Check
The current characters A[i-1] and B[j-1] are equal. Which update is correct?
Recap: LCS
Build an n+1 by m+1 table: on a match add one to the diagonal, else take the max neighbor. The corner holds the length. 🔗
Frequently asked questions
Is the “Longest Common Subsequence” lesson free?
Yes — the full text of “Longest Common Subsequence” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Longest Common Subsequence”?
Align two strings with a DP table. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Longest Common Subsequence” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Path Counting on a Grid
- Minimum Path Sum with Obstacles
- Longest Common Subsequence
- Edit Distance Step by Step