Skip to main content

19. Longest Common Subsequence

mediumAsked at Tesla

Find the longest subsequence shared by two strings — Tesla applies this DP pattern when diffing firmware build manifests to identify unchanged module sequences across OTA update versions before deciding what to re-flash.

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 (or none) from a string without reordering the remaining characters. Return 0 if no common subsequence exists.

Constraints

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

Examples

Example 1

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

Explanation: The longest common subsequence is "ace" with length 3.

Example 2

Input
text1 = "bl", text2 = "yby"
Output
1

Approaches

1. 2D DP table

Build an (m+1)x(n+1) table where dp[i][j] = LCS length for text1[0..i-1] and text2[0..j-1]. Match extends diagonal; mismatch takes max of left/above.

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:

2. Space-optimized rolling rows

Keep only two rows of the DP table at a time, reducing space from O(m*n) to O(n) while maintaining the same runtime.

Time
O(m*n)
Space
O(n)
function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  let prev = new Array(n + 1).fill(0);
  for (let i = 1; i <= m; i++) {
    const curr = new Array(n + 1).fill(0);
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        curr[j] = prev[j - 1] + 1;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }
    prev = curr;
  }
  return prev[n];
}

Tradeoff:

Tesla-specific tips

Tesla's embedded software team cares about this pattern in the context of delta OTA updates — only reflash what changed. Interviewers like to hear you explain the dp[i][j] recurrence in plain English before writing code. After solving, they often ask you to reconstruct the actual subsequence (backtrack through the dp table) — have that backtrack loop ready mentally.

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

Practice these live with InterviewChamp.AI →