Algorithm Vision
Dynamic ProgrammingIntermediate

Longest Common Subsequence (LCS)

Finds the longest subsequence present in two sequences in the same order. Uses dynamic programming to build a solution table. Applications include DNA sequence alignment, file difference tools (diff), and plagiarism detection.

#dynamic-programming#strings#sequences#optimization

Complexity Analysis

Time (Average)

O(m × n)

Expected case performance

Space

O(m × n)

Memory requirements

Time (Best)

O(m × n)

Best case performance

Time (Worst)

O(m × n)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 15•Section 15.4

LCS finds the longest subsequence common to both strings

Step: 1 / 0
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default
Comparing
Swapped
Sorted

Code Execution

Currently executing
Previously executed

Implementation

Related Algorithms

View all in Dynamic Programming

Matrix Chain Multiplication

Advanced

Finds the optimal way to parenthesize a chain of matrices to minimize the number of scalar multiplications. Classic dynamic programming problem from CLRS Chapter 15.

O(n³)
O(n²)
dynamic-programmingoptimization
Start Learning

Fibonacci (Dynamic Programming)

Beginner

Computes Fibonacci numbers efficiently using dynamic programming to avoid redundant calculations. Demonstrates the power of memoization in transforming an exponential-time recursive solution into a linear-time algorithm. A classic introduction to dynamic programming concepts.

O(n)
O(n)
dynamic-programmingmemoization
Start Learning

Edit Distance (Levenshtein)

Intermediate

Dynamic programming algorithm that calculates the minimum number of single-character edits (insertions, deletions, substitutions) required to transform one string into another. Fundamental in spell checking, DNA sequence alignment, and natural language processing.

O(m × n)
O(m × n)
dynamic-programmingstrings
Start Learning
Back to Dynamic Programming
Longest Common Subsequence (LCS) - Algorithm Vision