Longest Common Subsequence

Examples

Input: text1 = "abcde", text2 = "ace"
Output: 3

"ace" is the longest string that is a subsequence of both.

Input: text1 = "abc", text2 = "abc"
Output: 3

Input: text1 = "abc", text2 = "def"
Output: 0

The two strings share no characters at all.

Constraints

• 1 <= text1.length, text2.length <= 1000

• Both strings contain only lowercase English letters

Approach

Think of building a table where cell (i, j) answers: "what is the longest common subsequence between the first i characters of text1 and the first j characters of text2?"

If the i-th character of text1 and the j-th character of text2 are the same letter, that letter can always be safely used in the answer — so the answer for (i, j) is 1 plus the answer for (i-1, j-1) (both strings with that matching character removed).

If they're different letters, the matching character isn't shared at this position, so the best you can do is whichever is better: dropping the last character of text1 (answer for (i-1, j)) or dropping the last character of text2 (answer for (i, j-1)).

An empty prefix of either string can never share anything, so the first row and first column of the table are all 0 — that's your base case.

Solutions

Brute Force — Recursion

Walk both strings from the front. If the current characters match, take that character and recurse on both strings advanced by one. Otherwise, try skipping a character from either string and keep the better result. This revisits the same (i, j) pairs repeatedly.

function longestCommonSubsequence(text1, text2) {
  function lcs(i, j) {
    if (i === text1.length || j === text2.length) return 0;
    if (text1[i] === text2[j]) return 1 + lcs(i + 1, j + 1);
    return Math.max(lcs(i + 1, j), lcs(i, j + 1));
  }
  return lcs(0, 0);
}

Time: O(2^(m + n)) · Space: O(m + n) — recursion depth

Optimal — Bottom-Up 2D Table

Build a table indexed by (prefix length of text1, prefix length of text2). Row and column 0 start at 0 because an empty prefix shares nothing. Fill the rest left to right, top to bottom: extend the diagonal answer by one on a match, otherwise carry forward the better of the cell above or the cell to the left.

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;
  const table = 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]) {
        table[i][j] = table[i - 1][j - 1] + 1;
      } else {
        table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
      }
    }
  }

  return table[m][n];
}

Time: O(m * n) · Space: O(m * n)