Git Diff LCS Application

How does Git diff utilize the Longest Common Subsequence algorithm?

Edit Distance (Levenshtein Distance)

Given two strings word1 and word2, return minimum operations (insert, delete, replace) to convert word1 into word2.

Shortest Common Supersequence

Find the shortest string that has both str1 and str2 as subsequences.

Dynamic Programming & AdvancedIntermediate LevelStudy Time: 25 mins

Longest Common Subsequence Algorithm

Longest Common Subsequence (LCS) finds the longest subsequence present in two sequence strings in the same relative order using Dynamic Programming.

Longest Common Subsequence (LCS)

Strings loaded. Click Compute LCS to build the dynamic programming grid and backtrack the sequence.

Click Compute LCS to generate the DP matrix grid.

Speed:

LCS Dynamic Programming Matrix Worked Trace

Sample Input:String A: 'stone', String B: 'longest'

Step 1

Initialize DP Grid Matrix

Create (M+1) x (N+1) grid filled with 0s for base string empty prefixes.

dp[0][j] = 0, dp[i][0] = 0

Grid stores max LCS length for all prefixes.

Step 2

Match Characters & Increment DP

When A[i-1] == B[j-1] (e.g. 's' matches 's', 'o' matches 'o'), set dp[i][j] = 1 + dp[i-1][j-1].

Matches found: 'o', 'n', 'e'

Matches accumulate diagonal values.

Step 3

Reconstruct Longest Subsequence

Trace back from dp[M][N] to extract matched characters 'one'.

Longest Common Subsequence: 'one' (Length = 3)

Computes exact longest common subsequence in O(M × N) time.

Real-world analogy: DNA Strand Comparison

Subsequence vs Substring

Hover over items for details

Compare two DNA gene codes to find matching mutation sequences while ignoring unmapped intermediate genes.

Subsequence vs Substring= Subsequences do not need to occupy contiguous memory positions.

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapLongest Common Subsequence: O(N × W) Memoized Time

Hover curves to inspect classes

Time Steps (N=500)

500 steps (Linear)

O(N × W) Memoized Time

Space Footprint

O(N × W) Cache Matrix

Memory growth rate as N expands.

Performance Rank

Efficient Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
LCS DP Matrix	O(M × N)	O(M × N)

Code implementations

function lcs(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[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[m][n];
}