9.4 Longest Common Subsequence (LCS)

Demo: Longest Common Subsequence — LC 1143 (Medium — Amazon/Google/Meta High)

Statement (Demo): Given strings text1 and text2, return the length of their longest common subsequence. Example: text1="abcde", text2="ace" → 3 ("ace") | ⚡ len(text1), len(text2) ≤ 1000

Approach: If the last characters match, consume both: diagonal + 1. If not, drop the last character of either string and take the larger result.

function longestCommonSubsequence(s1, s2) {
  const m = s1.length,
    n = s2.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++)
      dp[i][j] =
        s1[i - 1] === s2[j - 1]
          ? dp[i - 1][j - 1] + 1
          : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[m][n];
}

Complexity: Time O(m·n), Space O(m·n) (O(n) keeping two rows)