Skip to main content

20. Longest Common Subsequence

mediumAsked at JetBrains

Find the longest sequence appearing as a subsequence in both strings — JetBrains uses this to test the DP foundation under their diff and merge tooling.

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

Problem

Given two strings text1 and text2, return the length of their longest common subsequence. If none exists, return 0.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Plain recursion

Branch on match/no-match at each index pair without memoization; exponential.

Time
O(2^(m+n))
Space
O(m+n)
function rec(i,j){ if (i<0||j<0) return 0; if (a[i]===b[j]) return 1+rec(i-1,j-1); return Math.max(rec(i-1,j),rec(i,j-1)); }

Tradeoff:

2. Bottom-up DP table

dp[i][j] = LCS of text1[0..i] and text2[0..j]; equal characters extend, otherwise take the best of dropping one side. Same DP shape JetBrains diff engines use to align tokens.

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

Tradeoff:

JetBrains-specific tips

JetBrains expects you to mention that LCS is the algorithmic core of textual diff — exactly the shape powering their inline VCS diff view and merge-conflict UI.

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 JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →