What is a Longest Common Subsequence Visualizer?
A longest common subsequence visualizer shows the longest sequence of characters that appears in two strings in the same relative order. The characters do not need to be contiguous.
This tool lets you enter two strings, fill the LCS dynamic programming table, and backtrack one valid longest common subsequence.
For the full algorithm set, browse the Data Structure Visualizers hub.
How to use this LCS visualizer
- Enter the first string.
- Enter the second string.
- Click Run LCS to fill the table and show the final subsequence.
- Step forward to inspect each match, top-cell reuse, or left-cell reuse.
- Read the backtracked sequence and length in the output panel.
LCS and dynamic programming
LCS is a standard dynamic programming problem because each table cell depends on smaller prefixes of the two strings. A character match takes the diagonal value plus one; a mismatch keeps the better of the top and left cells.
For related table-based string DP, compare this page with the Edit Distance Visualizer. To practice another reusable-subproblem DP pattern, try the Coin Change DP Visualizer. For non-DP string matching, use the KMP String Matching Visualizer.