Longest Common Subsequence Visualizer

Watch the LCS dynamic programming grid fill and backtrack to reveal a longest common subsequence with step-by-step explanations.

Current status: Ready. Use the controls to begin exploring Longest Common Subsequence.

Longest Common Subsequence Visualizer

∅BDCABA
∅
0
0
0
0
0
0
0
A
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0
C
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0
D
0
0
0
0
0
0
0
A
0
0
0
0
0
0
0
B
0
0
0
0
0
0
0

Base case: an empty string has an LCS of length 0 with anything.

Step 1 / 43

Animation Legend

Dependency Cell(s)
Cell Being Computed
Backtracked LCS Path

When characters match, the value comes diagonally from dp[i-1][j-1] plus one. When they don't match, the value is the maximum of the cell above and the cell to the left. Once the table is complete, the algorithm backtracks from the bottom-right corner (Purple) to reconstruct the actual subsequence.

Java Implementation

public int lcs(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][m];
}

What is the Longest Common Subsequence problem?

The Longest Common Subsequence (LCS) of two strings is the longest sequence of characters that appears in both strings in the same relative order, but not necessarily contiguously. For example, the LCS of "ABCBDAB" and "BDCABA" is "BCBA", with length 4.

LCS is solved with a 2D DP table where dp[i][j] represents the length of the LCS between the first i characters of string one and the first j characters of string two. Just like the Knapsack Problem, each cell is built from previously solved subproblems, avoiding the exponential cost of checking every possible subsequence.

Time & Space Complexity

  • Brute ForceO(2^n)
  • DP TimeO(n · m)
  • DP SpaceO(n · m)
  • Optimized SpaceO(min(n, m))

* n and m are the lengths of the two input strings.

Real-World Use Cases

  • ✓
    Diff Tools & Version ControlTools like Git use LCS-based algorithms to compute differences between file versions.
  • ✓
    BioinformaticsComparing DNA, RNA, or protein sequences to find shared genetic patterns.
  • ✓
    Plagiarism DetectionMeasuring textual similarity between documents.

Concept guide

Review the mental model, tradeoffs, and practical use cases after you experiment.

Longest Common Subsequence Complete Info Card

Dynamic ProgrammingString Matching

The Longest Common Subsequence algorithm fills a 2D table where each cell dp[i][j] stores the length of the LCS between the first i characters of one string and the first j characters of another, then backtracks to reconstruct the actual subsequence.

Algorithm Characteristics

Time Complexity (Brute Force)

Checks every possible subsequence

O(2^n)

Time Complexity (DP)

n and m are the two string lengths

O(n · m)

Space Complexity (DP)

Full 2D table of one string vs. the other

O(n · m)

Space Complexity (Optimized)

Only two rows are needed for the length itself

O(min(n, m))

Optimal Substructure

dp[i][j] built from smaller prefixes

Yes

Reconstruction

Walk the table to recover the actual subsequence

Backtracking

DP Table Fill Steps

1

Initialize dp[0][*] and dp[*][0] to 0

2

Compare characters s1[i-1] and s2[j-1]

3

If equal: dp[i][j] = dp[i-1][j-1] + 1

4

If not equal: dp[i][j] = max(top, left)

5

Repeat for every cell in the table

6

Backtrack from dp[n][m] to rebuild the LCS

Optimization Techniques

Two-Row Rolling Array

Only the previous row is needed to compute the next

prevRow, currRow = currRow, prevRow

Diagonal Tracking

Save dp[i-1][j-1] before overwriting it in-place

diag = prevDiag; prevDiag = curr;

When to Use

  • •Diffing files or computing edit distance variants
  • •Comparing DNA, RNA, or protein sequences
  • •Measuring similarity between two ordered sequences

When to Avoid

  • •Very long strings (table grows as n × m)
  • •When contiguous substrings are needed instead (use Longest Common Substring)
  • •Only the length is needed and memory is extremely tight
Did You Know? The Unix diff command and Git's merge logic are both built on LCS-style algorithms.
String comparisonBioinformaticsDiff tools