🧬 Longest Common Subsequence
DP alignment grid
Cell 0 / 0
LCS: —
Strings
Controls
Stats
Cells filled
0
LCS length
—
Phase
Fill
Status
Ready
Matches
Info & Theory

The longest common subsequence (LCS) of two strings is the longest run of characters appearing in both in the same order, but not necessarily next to each other.

The DP recurrence

Let L[i][j] be the LCS length of the first i characters of A and first j of B:

  • L[0][j] = L[i][0] = 0.
  • If A[i] = B[j]: L[i][j] = L[i−1][j−1] + 1 (a diagonal match).
  • Otherwise L[i][j] = max(L[i−1][j], L[i][j−1]).

Recovering the subsequence

From the bottom-right cell, walk back: on a match move diagonally and keep the character; otherwise step toward the larger neighbour. Reverse the collected characters to get the LCS.

Complexity

The grid has (m+1)×(n+1) cells, so the algorithm runs in O(m·n) time and space.

Where it is used

The diff utility, version control, DNA sequence comparison and plagiarism detection are all powered by LCS.

Frequently asked questions

What is the longest common subsequence?

The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both, in the same order, but not necessarily contiguously.

How is a subsequence different from a substring?

A substring is a contiguous run of characters, while a subsequence keeps the original order but may skip characters. ACE is a subsequence of ABCDE but not a substring.

How does the DP grid solve LCS?

Cell L[i][j] holds the LCS length of the first i characters of one string and the first j of the other. If the characters match, it is the diagonal value plus one; otherwise it is the larger of the cell above or to the left.

Why does a diagonal step mean a match?

A diagonal step consumes one character from each string at once. The DP only takes that step when those two characters are equal, so each diagonal on the path is a matched character of the LCS.

How is the subsequence recovered?

Starting at the bottom-right cell, you walk back: on a match you move diagonally and prepend the character, otherwise you move toward the larger neighbour. The collected characters, reversed, form the LCS.

What is the time complexity?

Filling the grid takes O(m·n) time and O(m·n) space for two strings of length m and n. Reconstruction adds only O(m+n).

Where is LCS used in practice?

Diff and version-control tools, DNA and protein sequence comparison, plagiarism detection and data merging all rely on LCS to find shared structure.

Is the LCS always unique?

The length is unique, but several different subsequences can reach that maximum length. The backtracking shown here recovers one valid LCS.

How does LCS relate to edit distance?

When only insertions and deletions are allowed, the edit distance equals m + n − 2·LCS. LCS and Levenshtein distance are closely related alignment problems.

Can LCS handle more than two sequences?

Yes, but the DP table gains a dimension per sequence, so the problem becomes NP-hard for an arbitrary number of sequences. This simulation handles the classic two-string case.

About Longest Common Subsequence

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 5 July 2026

The Longest Common Subsequence (LCS) problem finds the longest sequence of characters (not necessarily contiguous) that appears in the same relative order in both input strings. It is solved in O(mn) time and space using dynamic programming: a table L[i][j] stores the LCS length of the first i characters of string A and the first j characters of string B, with the recurrence L[i][j] = L[i−1][j−1] + 1 if A[i]=B[j], else max(L[i−1][j], L[i][j−1]). LCS underpins the Unix diff utility, DNA sequence alignment, and plagiarism detection tools, where it identifies the maximum common structure between two documents or genomes.

This simulation fills the DP table cell by cell, then backtracks to highlight all optimal alignment paths through the matrix. You can also see how the LCS relates to edit distance: the minimum insertions and deletions needed to transform A into B equals (|A| + |B| − 2·LCS(A, B)), making the two problems dual views of the same underlying structure.

Frequently Asked Questions

What is the recurrence relation for LCS?

L[i][j] = 0 if i=0 or j=0 (empty string base case); L[i][j] = L[i−1][j−1] + 1 if A[i] = B[j] (characters match, extend LCS); L[i][j] = max(L[i−1][j], L[i][j−1]) otherwise (take the better of skipping one character from either string). Backtracking from L[m][n] following diagonal moves (match) and the direction of the max recovers the actual LCS string.

Is the LCS unique?

No — there can be multiple LCS of the same maximum length. For example, LCS("ABCB", "BDCAB") has length 3, with both "BCB" and "BCA" being valid longest common subsequences. The number of distinct LCS can be exponential in the string lengths in the worst case. Backtracking through the DP table may yield any one of these; enumerating all requires additional bookkeeping.

How does LCS relate to edit distance?

When only insertions and deletions are allowed (no substitutions), edit distance(A, B) = |A| + |B| − 2·LCS(A, B). Every matched character in the LCS avoids one deletion and one insertion, saving 2 operations. Levenshtein distance adds substitutions as an optional shortcut (cost 1 instead of delete+insert = cost 2). The two DP tables are structurally identical, differing only in how the diagonal (mismatch) cell is computed.

What is the Hunt-Szymanski algorithm for sparse LCS?

For sequences with few matching pairs (sparse match sets), the Hunt-Szymanski algorithm finds LCS in O((r + n) log n) time where r is the number of matching positions. It first enumerates all (i, j) pairs where A[i]=B[j], then finds the longest increasing chain in these pairs by y-coordinate — equivalent to the longest increasing subsequence problem. This is much faster than O(mn) when the alphabet is large or the sequences share few characters.

Can LCS be computed faster than O(mn)?

For general sequences over an arbitrary alphabet, the best known algorithms run in O(mn/log n) using word-level parallelism (bit-vector methods). For small alphabets, the Four-Russians method achieves O(mn/log2 n). For random strings over an alphabet of size k, the expected LCS length is approximately γ·n where γ depends on k (e.g., γ ≈ 0.8 for binary), and algorithms exploiting this structure can be faster in practice.

How does the Unix diff command use LCS?

Unix diff computes the LCS of two files treated as sequences of lines. Lines in the LCS are "unchanged"; lines in file A but not in the LCS are "deleted" (marked with −); lines in file B but not in the LCS are "added" (marked with +). The output is the minimal edit script to transform one file into the other. Git's diff algorithm (patience diff, histogram diff) uses LCS variants with heuristics to produce more human-readable diffs for typical source code.

What is the Longest Common Substring problem, and how does it differ from LCS?

The Longest Common Substring (not subsequence) requires the matching characters to be contiguous in both strings. It is solved in O(mn) time with a DP table where L[i][j] = L[i−1][j−1]+1 if A[i]=B[j], else 0, and the answer is max(L[i][j]). More efficiently, a generalised suffix tree solves it in O(m+n) time. LCS ≥ longest common substring length in general, since subsequences are more flexible.

How is LCS applied in bioinformatics?

In DNA or protein sequence alignment, LCS identifies the conserved regions between two genomes or protein sequences. The Needleman-Wunsch algorithm (global alignment) is mathematically equivalent to LCS with configurable match scores and gap penalties. Identifying LCS-like conserved domains between human and mouse genomes reveals functionally important regions under evolutionary pressure, guiding gene annotation and drug target discovery.

What is the relationship between LCS and the Longest Increasing Subsequence?

LCS can be reduced to the Longest Increasing Subsequence (LIS) problem: replace each character in A with its rank among matches in B, then find the LIS of the resulting sequence of positions. Conversely, LIS can be solved in O(n log n) using patience sorting. The Hunt-Szymanski sparse LCS algorithm exploits exactly this reduction, giving O(r log n) for sparse match sets where r is the number of matching pairs.

How much memory does LCS require, and can it be reduced?

Standard DP uses O(mn) space for the full table. Hirschberg's algorithm (1975) computes LCS in O(mn) time but only O(min(m,n)) space by using divide and conquer: it splits the problem at the midpoint row, finds where the optimal LCS path crosses that row using linear space, then recurses on both halves. This is the same technique used in optimal space-efficient sequence alignment in bioinformatics.