Longest Common Subsequence (LCS) & 2D DP

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Subsequence vs. Substring

• A Substring must be contiguous (e.g. "bcd" in "abcdef").
• A Subsequence maintains relative order but does NOT need to be contiguous (e.g. "ace" is a subsequence of "abcde").

2. 2D DP State Transition

Let dp[i][j] be the LCS length of text1[0...i-1] and text2[0...j-1]:

• If characters match (text1[i - 1] === text2[j - 1]): $$ ext[i][j] = 1 + ext[i - 1][j - 1]$$
• If characters differ: $$ ext[i][j] = max( ext[i - 1][j], ext[i][j - 1])$$

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const 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] = 1 + dp[i - 1][j - 1]; // Diagonal + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // Max of top and left
      }
    }
  }

  return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace")); // Output: 3 ("ace")
console.log(longestCommonSubsequence("abc", "abc"));   // Output: 3
console.log(longestCommonSubsequence("abc", "def"));   // Output: 0

3. Visual 2D Grid for ("abcde", "ace")

       ""   a   c   e
  "" [  0,  0,  0,  0 ]
  a  [  0,  1,  1,  1 ]
  b  [  0,  1,  1,  1 ]
  c  [  0,  1,  2,  2 ]
  d  [  0,  1,  2,  2 ]
  e  [  0,  1,  2,  3 ]  ◄── dp[5][3] = 3

4. Applications of 2D Grid DP

• Git Diff Algorithm: Computing minimal line changes between commits.
• Edit Distance (Levenshtein Distance): Minimum inserts/deletes/replaces to transform string A into string B.
• DNA Sequence Alignment in bioinformatics.

5. Common Mistakes

• Index Misalignment: Forgetting that 1-indexed dp[i][j] corresponds to 0-indexed string characters text1[i - 1] and text2[j - 1].

6. Next Steps

Use 2D DP for string transformation and grid path problems. Next, let's explore the Intervals Pattern!