Skip to main content

21. Longest Common Subsequence

mediumAsked at Flipkart

Find the length of the longest common subsequence of two strings — Flipkart uses it to test 2-D DP fluency, the same shape used for fuzzy product-name dedupe.

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 keeps relative order but allows skipping characters; return 0 if none exists.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Naive recursion

Recurse on (i, j); branch on match vs skip-left vs skip-right.

Time
O(2^(m+n))
Space
O(m+n)
// exponential without memoization

Tradeoff:

2. Bottom-up DP

dp[i][j] is the LCS length of the first i characters of text1 and first j of text2. Match extends the diagonal; mismatch takes the max of the two neighbors.

Time
O(m*n)
Space
O(m*n)
function longestCommonSubsequence(a, b) {
  const m = a.length, n = b.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++) {
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1] + 1
        : Math.max(dp[i-1][j], dp[i][j-1]);
    }
  }
  return dp[m][n];
}

Tradeoff:

Flipkart-specific tips

Flipkart screeners reward the rolling-array O(n) memory upgrade as a follow-up — they hit memory limits on long product titles in their dedupe pipelines.

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

Practice these live with InterviewChamp.AI →