Skip to main content

15. Longest Common Subsequence

mediumAsked at GitHub

Classic DP problem that underlies git diff and merge algorithms used daily at GitHub to compute edit distances between file versions.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is formed by deleting some characters without changing the order of the remaining characters.

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • text1 and text2 consist of only lowercase English letters

Examples

Example 1

Input
text1 = 'abcde', text2 = 'ace'
Output
3

Example 2

Input
text1 = 'abc', text2 = 'abc'
Output
3

Approaches

1. Recursive without memoization

Recursively compare characters from both strings, branching on match vs skip — exponential without caching.

Time
O(2^(m+n))
Space
O(m+n)
// lcs(i, j): if text1[i]==text2[j], return 1 + lcs(i+1,j+1)
// else return max(lcs(i+1,j), lcs(i,j+1))
// Exponential: recomputes same subproblems

Tradeoff:

2. Bottom-up DP table

Build an (m+1)×(n+1) table where dp[i][j] is the LCS of text1[0..i-1] and text2[0..j-1]. Fill row by row using the recurrence.

Time
O(m*n)
Space
O(m*n)
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] = 1 + dp[i-1][j-1];
      } else {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  return dp[m][n];
}

Tradeoff:

GitHub-specific tips

GitHub asks this because it's the heart of `git diff` — bonus points for discussing how Myers' diff algorithm optimizes LCS and how backtracking the DP table reconstructs the actual diff hunks.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Longest Common Subsequence and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →