Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

Longest Common Subsequence

Problem (restated)

Lengths of longest subsequence common to text1 and text2 (not necessarily contiguous).

Intuition

dp[i][j] = LCS of prefixes. Equal → +1 diagonal; else max(skip either).

Approaches

Classic LCS DP

Unverified

Time O(mn)Space O(min(m,n))

Idea. 1D rolling: dp[j] previous row; track prev diagonal carefully.

Walkthrough. abcde vs ace → 3.

Trade-offs. Edit distance is the same grid with different recurrences.

Solution

export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    let prev = 0;
    for (let j = 1; j <= n; j++) {
      const tmp = dp[j]!;
      if (text1[i - 1] === text2[j - 1]) dp[j] = prev + 1;
      else dp[j] = Math.max(dp[j]!, dp[j - 1]!);
      prev = tmp;
    }
  }
  return dp[n]!;
}

export function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    let prev = 0;
    for (let j = 1; j <= n; j++) {
      const tmp = dp[j]!;
      if (text1[i - 1] === text2[j - 1]) dp[j] = prev + 1;
      else dp[j] = Math.max(dp[j]!, dp[j - 1]!);
      prev = tmp;
    }
  }
  return dp[n]!;
}

Template connection

Two-dimensional DP on two strings.

Reflection

Equal letters take the previous diagonal plus 1. Otherwise take max(above, left). The first row and the first column are 0.
On a rolling row, save the old diagonal before you overwrite the cell. Reading the value you just wrote uses the current row.
A subsequence is not a substring; order is what matters. One string empty is 0. Identical strings answer their length. No shared letter is 0.