✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-177

Longest Common Subsequence (LCS)

Learn how dynamic programming finds the longest sequence of elements shared by two sequences while preserving their relative order.

Explanation

Overview

The Longest Common Subsequence problem finds the longest sequence that appears in two given sequences in the same relative order. The selected elements do not need to be adjacent in either original sequence.

Key concepts

Subsequence; Prefix-based states; Matching elements; Optimal substructure; Table reconstruction

Variables

X: The first input sequence.; Y: The second input sequence.; i: The number of elements considered from X.; j: The number of elements considered from Y.; dp[i][j]: The length of the LCS of the first i and first j elements.

Complexity

tabulation: O(mn) time and O(mn) space.; spaceOptimized: O(mn) time and O(min(m,n)) space when only the length is required.; variables: m and n are the lengths of the two input sequences.

Example

sequenceX: ABCBDAB; sequenceY: BDCABA; oneLongestCommonSubsequence: BCBA; length: 4; explanation: The characters B, C, B, and A appear in both sequences in the same relative order, even though they are not necessarily adjacent.

Pseudocode

function LCS(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1) filled with 0
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]

Applications

Text comparison.; Version-control diff tools.; DNA and protein sequence analysis.; Similarity measurement.; File comparison.

Variables

X

The first input sequence.

Y

The second input sequence.

I

The number of elements considered from X.

J

The number of elements considered from Y.

Dp[i][j]

The length of the LCS of the first i and first j elements.

Example or application

Sequence X

ABCBDAB

Sequence Y

BDCABA

One Longest Common Subsequence

BCBA

Length

4

Explanation

The characters B, C, B, and A appear in both sequences in the same relative order, even though they are not necessarily adjacent.

Definition

The Longest Common Subsequence problem finds the longest sequence that appears in two given sequences in the same relative order. The selected elements do not need to be adjacent in either original sequence.

Mathematical Representation

If X[i-1] = Y[j-1], dp[i][j] = 1 + dp[i-1][j-1]; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Approaches

Recursive

Compares the final elements of the two prefixes and explores smaller prefix combinations.

Memoization

Stores previously calculated prefix-pair results.

Tabulation

Builds a two-dimensional table from empty prefixes toward the complete sequences.

Reconstruction

Traces backward through the table to recover one longest common subsequence.

Pseudocode

function LCS(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1) filled with 0
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]

Complexity

Tabulation

O(mn) time and O(mn) space.

Space Optimized

O(mn) time and O(min(m,n)) space when only the length is required.

Variables

m and n are the lengths of the two input sequences.

Key Concepts

  • Subsequence

  • Prefix-based states

  • Matching elements

  • Optimal substructure

  • Table reconstruction

Advantages

  • Finds the longest order-preserving shared sequence.

  • Supports text comparison and sequence analysis.

  • Can reconstruct an actual common subsequence.

  • Demonstrates two-dimensional dynamic programming.

Limitations

  • The standard table requires O(mn) time and memory.

  • Large sequences may make the full table expensive.

  • Multiple different longest common subsequences may exist.

Applications

  • Text comparison.

  • Version-control diff tools.

  • DNA and protein sequence analysis.

  • Similarity measurement.

  • File comparison.

Related Topics

  • Longest Increasing Subsequence

  • Edit Distance Problem

  • String Algorithms

  • Dynamic Programming

Practice Question

What is the length of an LCS for ABC and AC?

Practice Answer

2. One longest common subsequence is AC.

Learning Objectives

  • Explain the central idea and purpose of longest common subsequence (lcs).

  • Identify the assumptions, inputs, and conditions relevant to longest common subsequence (lcs).

  • Evaluate an application of longest common subsequence (lcs) for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures