Skip to content
Scrollchart
Computing Medium #dp#lcs#string-algorithms

Longest Common Subsequence

A DP grid finds the longest shared sequence between two strings. Foundation of diff and version control.

A free, animated longest common subsequence you can read here or embed on any website, from Scrollchart.

Longest Common Subsequence

Longest Common SubsequenceMatch chars bump the diagonal; mismatches take max(left, up). LCS = 3 chars shared by AGCAT and GACTA.

Two strings frame a 2D table. Matching characters bump the diagonal cell by 1; mismatches take the max of left/up. The LCS is read out by walking diagonals on match. Connection to git diff and Levenshtein distance is annotated.

Good for

  • CS courses on dynamic programming and string algorithms
  • Articles explaining how git diff and patch files work
  • Bioinformatics tutorials on sequence alignment

Source & accuracy

This longest common subsequence is an editorial illustration built to represent the concept accurately. Where it shows figures, they are typical or representative values chosen to make the relationship clear, not a single underlying dataset. The diagram and its explainer are reviewed and maintained centrally, and updated over time as understanding improves.

Building the similarity matrix

The longest common subsequence (LCS) problem asks: given two strings, what is the longest sequence of characters that appears in both (not necessarily contiguous)? DP builds a 2D table where entry (i, j) holds the length of the LCS of the first i characters of string A and the first j characters of string B. If characters match, the entry is 1 plus the diagonal entry (from i-1, j-1). If they do not match, it is the maximum of the left or top entry (from i-1 or j-1).

Recovering the actual subsequence

The table alone gives the LCS length. To find the actual characters, you traceback from the bottom-right corner: if characters matched at an entry, include that character and move diagonally; otherwise, move toward the larger neighbor. This reconstructs the sequence. LCS is the foundation of diff algorithms (comparing file versions), version control, and sequence alignment in bioinformatics. The O(m*n) DP solution is practical for strings up to thousands of characters.

Embed this diagram

Add this animated longest common subsequence to your own site. Copy one line of HTML, or use the embed builder for theme and sizing options.

Reference

What this is
A free, embeddable, animated longest common subsequence for any website.
Who uses it
Developer blogs, CS educators.
How to embed
Copy one line of HTML. No signup. No watermark. Works in WordPress, Webflow, Ghost, Substack, plain HTML.
File size
iframe embed, ~80 KB gzipped (loads on demand, does not block your page paint).
License
Free forever. Editorial explainer text included; updated centrally over time.
URL
scrollchart.com/diagram/lcs-dp

Embed format options

Copy the universal HTML snippet, the WordPress shortcode, or an iframe fallback - see the WordPress plugin page for details. Any format keeps the same Core Web Vitals profile and the same explainer text.

Embed snippet 
<div data-scrollchart="lcs-dp" data-scrollchart-v="1"></div>
<script src="https://scrollchart.com/embed.js" async></script>

By embedding, you acknowledge the diagram and explainer text are served from scrollchart.com and may be updated from time to time to reflect new research or to link to relevant sources within the explainer.

Frequently asked questions

Where can I get a free animated "Longest Common Subsequence" for my website?
Scrollchart provides "Longest Common Subsequence" as a free, embeddable animated diagram you can add to any website with one line of HTML. No signup is required and there is no watermark. The diagram and its explainer text are served from scrollchart.com, so the embed stays current without any maintenance on your end.
How do I embed a longest common subsequence in a developer or tech blog?
Copy the one-line snippet from the Scrollchart diagram page and paste it into your post HTML. It works in any static site generator, CMS, or hand-coded HTML page. The embed is a thin loader, not an iframe, so the content is fully in your DOM.
Related diagrams

Other computing explainers

See all computing →
Computing Medium

Levenshtein Edit Distance

Min insertions/deletions/substitutions to turn one string into another. The DP grid that powers spellcheck.
Computing Medium

0/1 Knapsack: DP Table Fill

A 2D table fills in row by row. Each cell takes the best of "skip" or "include the current item".
Computing Medium

Greedy vs DP: When Greedy Fails

Coin change with US coins works greedily. With {1,3,4} and target 6 it produces a wrong answer.