Longest Common Subsequence
Align two strings with a DP table.
Longest Common Subsequence is a free Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy 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 Competitive Programming Academy course, upgrade to CoddyKit PRO.
What will I learn in “Longest Common Subsequence”?
Align two strings with a DP table. You practise Competitive Programming Academy 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 Competitive Programming Academy?
No prior experience is required. Competitive Programming Academy 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 Competitive Programming Academy lesson?
Yes. Every Competitive Programming Academy 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