Longest Common Subsequence

1. Define the problem

Given two strings text1 and text2, return the length of their longest common subsequence . If there is no common subsequence, return 0. A subsequence keeps the original order of characters but can skip any of them — it is not the same as a contiguous substring . When the current characters of both strings match, extend the best match found without them. Otherwise, take the better of dropping a character from either string — two smaller subproblems solved one row earlier.

Constraints

1 ≤ text1.length, text2.length ≤ 1000
text1 and text2 consist of only lowercase English characters

Example

Inputtext1 = "abcde", text2 = "ace"

Output3

Explanation The longest common subsequence is "ace", length 3.

2. Know the words first

In plain terms

Subsequence vs. substring: A subsequence can skip characters but must keep their order, like 'ace' from 'abcde'. A substring must be a contiguous run, like 'bcd' from 'abcde'.

3. Visualize the solution

Fill one row per character, matching or carrying forward the best

Statusrow for a (i=1)

text1="abcde", text2="ace". "a" matches text2[0] — row = [0, 1, 1, 1].

What happens in this step

i = 1, text1[0] = 'a'
j=1 'a': matches text2[0]='a' → dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1
j=2 'c': 'a' !== 'c' → dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1
j=3 'e': 'a' !== 'e' → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 1) = 1

row = [0, 1, 1, 1]

Step 1 of 5

Steps to visualize

Build a table with one row per character of text1 and one column per character of text2, plus an empty row and column of zeros.
When the row's character matches the column's character, take the value diagonally above-left and add 1.
Otherwise, take the larger of the value directly above or directly to the left.
The bottom-right cell holds the length of the longest common subsequence.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill one row per character, matching or carrying forward the best

Statusrow for a (i=1)

text1="abcde", text2="ace". "a" matches text2[0] — row = [0, 1, 1, 1].

What happens in this step

i = 1, text1[0] = 'a'
j=1 'a': matches text2[0]='a' → dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1
j=2 'c': 'a' !== 'c' → dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1
j=3 'e': 'a' !== 'e' → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 1) = 1

row = [0, 1, 1, 1]

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

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] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}

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

6. Test cases

Test cases

Input	Expected	Covers
`text1 = "abcde", text2 = "ace"`	`3`	example from the docstring
`text1 = "abc", text2 = "abc"`	`3`	identical strings, the whole string matches
`text1 = "abc", text2 = "def"`	`0`	no characters in common at all
`text1 = "", text2 = "abc"`	`0`	one string is empty
`text1 = "", text2 = ""`	`0`	both strings are empty
`text1 = "a", text2 = "a"`	`1`	smallest non-trivial matching case
`text1 = "aggtab", text2 = "gxtxayb"`	`4`	a well-known case with the match interleaved through both strings

Longest Common Subsequence