Home/Algorithms/Longest Common Subsequence (LCS)

AvailablemediumDynamic Programming

Longest Common Subsequence (LCS)

Longest Common Subsequence (LCS) explained step-by-step: 2D dynamic programming grid construction, character matching rules, string reconstruction backtrack, diff algorithms, and JavaScript implementation.

Time O(m · n)Space O(m · n)Stable YesIn-place No

Introduction

What is Longest Common Subsequence (LCS)?

The Longest Common Subsequence (LCS) problem finds the longest sequence that can be derived from two strings by deleting zero or more characters without altering the relative ordering of the remaining characters.

LCS forms the mathematical engine behind version control diff tools (like `git diff`), DNA sequence alignment in computational genomics, file comparison utilities, and speech recognition engines. By constructing an (m + 1) × (n + 1) DP table, LCS computes optimal alignment in O(m · n) time.

Algorithm Overview

How it works

1
Initialize 2D DP Table
Create a table `dp[m+1][n+1]` filled with 0s. The extra 0th row and column handle base cases where either string is empty (length 0).
2
Character Match (Diagonal Transition)
If `text1[i-1] === text2[j-1]`, extend the best previous match without either character: `dp[i][j] = 1 + dp[i-1][j-1]`.
3
Character Mismatch (Max from Top or Left)
If `text1[i-1] !== text2[j-1]`, take the maximum achievable by dropping either the current character of text1 or text2: `dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])`.
4
Extract Length and Backtrack String
`dp[m][n]` yields the maximum subsequence length. Backtrack from cell `(m, n)` to `(0, 0)` following the diagonal transitions to reconstruct the actual LCS string.

lcs.js

1function longestCommonSubsequence(text1, text2) {
2  const m = text1.length;
3  const n = text2.length;
4 
5  // Initialize (m + 1) x (n + 1) DP matrix with zeros
6  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
7 
8  // Build DP table bottom-up
9  for (let i = 1; i <= m; i++) {
10    for (let j = 1; j <= n; j++) {
11      if (text1[i - 1] === text2[j - 1]) {
12        // Characters match: take diagonal + 1
13        dp[i][j] = 1 + dp[i - 1][j - 1];
14      } else {
15        // Characters differ: take best of excluding either character
16        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
17      }
18    }
19  }
20 
21  return dp[m][n];
22}
23 
24// Function to reconstruct the actual LCS string
25function getLCSString(text1, text2) {
26  const m = text1.length;
27  const n = text2.length;
28  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
29 
30  for (let i = 1; i <= m; i++) {
31    for (let j = 1; j <= n; j++) {
32      if (text1[i - 1] === text2[j - 1]) {
33        dp[i][j] = 1 + dp[i - 1][j - 1];
34      } else {
35        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
36      }
37    }
38  }
39 
40  let i = m, j = n;
41  const lcsChars = [];
42 
43  while (i > 0 && j > 0) {
44    if (text1[i - 1] === text2[j - 1]) {
45      lcsChars.push(text1[i - 1]);
46      i--;
47      j--;
48    } else if (dp[i - 1][j] > dp[i][j - 1]) {
49      i--;
50    } else {
51      j--;
52    }
53  }
54 
55  return lcsChars.reverse().join('');
56}
57 
58// Example usage:
59// longestCommonSubsequence('abcde', 'ace'); // 3
60// getLCSString('abcde', 'ace');             // 'ace'

Interactive Visualizer

Watch it run, step by step

Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.

Loading Interactive Visualizer...

Interactive Quiz

Test your knowledge

Practice Problems

Solve top interview questions

Coming Next

Interactive features on the way

The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.

Next update

Interactive 2D Matrix Heatmap

This feature will be implemented in the next update.

Next update

Diff String Alignment Trace

This feature will be implemented in the next update.

Next update

Edit Distance / Levenshtein Comparison

This feature will be implemented in the next update.

Back to all algorithms

Explore the full catalog — 30+ algorithms with more unlocking every release.

Browse Algorithms

Home/Algorithms/Longest Common Subsequence (LCS)

AvailablemediumDynamic Programming

Longest Common Subsequence (LCS)

Time O(m · n)Space O(m · n)Stable YesIn-place No

Introduction

What is Longest Common Subsequence (LCS)?

Algorithm Overview

How it works

1
Initialize 2D DP Table
Create a table `dp[m+1][n+1]` filled with 0s. The extra 0th row and column handle base cases where either string is empty (length 0).
2
Character Match (Diagonal Transition)
If `text1[i-1] === text2[j-1]`, extend the best previous match without either character: `dp[i][j] = 1 + dp[i-1][j-1]`.
3
Character Mismatch (Max from Top or Left)
If `text1[i-1] !== text2[j-1]`, take the maximum achievable by dropping either the current character of text1 or text2: `dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])`.
4
Extract Length and Backtrack String
`dp[m][n]` yields the maximum subsequence length. Backtrack from cell `(m, n)` to `(0, 0)` following the diagonal transitions to reconstruct the actual LCS string.

lcs.js

1function longestCommonSubsequence(text1, text2) {
2  const m = text1.length;
3  const n = text2.length;
4 
5  // Initialize (m + 1) x (n + 1) DP matrix with zeros
6  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
7 
8  // Build DP table bottom-up
9  for (let i = 1; i <= m; i++) {
10    for (let j = 1; j <= n; j++) {
11      if (text1[i - 1] === text2[j - 1]) {
12        // Characters match: take diagonal + 1
13        dp[i][j] = 1 + dp[i - 1][j - 1];
14      } else {
15        // Characters differ: take best of excluding either character
16        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
17      }
18    }
19  }
20 
21  return dp[m][n];
22}
23 
24// Function to reconstruct the actual LCS string
25function getLCSString(text1, text2) {
26  const m = text1.length;
27  const n = text2.length;
28  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
29 
30  for (let i = 1; i <= m; i++) {
31    for (let j = 1; j <= n; j++) {
32      if (text1[i - 1] === text2[j - 1]) {
33        dp[i][j] = 1 + dp[i - 1][j - 1];
34      } else {
35        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
36      }
37    }
38  }
39 
40  let i = m, j = n;
41  const lcsChars = [];
42 
43  while (i > 0 && j > 0) {
44    if (text1[i - 1] === text2[j - 1]) {
45      lcsChars.push(text1[i - 1]);
46      i--;
47      j--;
48    } else if (dp[i - 1][j] > dp[i][j - 1]) {
49      i--;
50    } else {
51      j--;
52    }
53  }
54 
55  return lcsChars.reverse().join('');
56}
57 
58// Example usage:
59// longestCommonSubsequence('abcde', 'ace'); // 3
60// getLCSString('abcde', 'ace');             // 'ace'

Interactive Visualizer

Watch it run, step by step

Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.

longest common subsequence Visualizer

Overlapping subproblem memoization & DP table animator

Step 1/8:LCS DP: Compare String 1 "ABC" vs String 2 "AC".

Loading Interactive Visualizer...

Interactive Quiz

Test your knowledge