Overview

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence is a sequence derived from another by deleting some or no elements without changing the order of remaining elements.

Constraints

• 1 <= text1.length, text2.length <= 1000
• Strings contain only lowercase English letters.
• Return an integer (the length, not the subsequence itself).

Examples

longestCommonSubsequence("abcde", "ace");
// => 3  (subsequence: "ace")

longestCommonSubsequence("abc", "abc");
// => 3  (identical strings)

longestCommonSubsequence("abc", "def");
// => 0  (no common characters)

Solution

function longestCommonSubsequence(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];
}

Resources

• Longest Common Subsequence — LeetCode
• LCS — Wikipedia