Skip to main content

1143. Longest Common Subsequence

medium

Find the length of the longest subsequence that appears in both strings, character order preserved but not contiguous. The reference 2D-DP-on-strings problem.

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

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 of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. A common subsequence of two strings is a subsequence that is common to both strings.

Constraints

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

Examples

Example 1

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

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

Example 2

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

Example 3

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Define dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1].

Hint 2

Recurrence: if text1[i-1] == text2[j-1], dp[i][j] = dp[i-1][j-1] + 1. Else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Hint 3

Base case: dp[0][*] = dp[*][0] = 0.

Solution approach

Reveal approach

2D bottom-up DP. Allocate dp[m+1][n+1] initialized to zeros. For i = 1..m and j = 1..n: if text1[i-1] == text2[j-1], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Return dp[m][n]. The +1 padding lets you reference dp[i-1] and dp[j-1] without boundary checks. Space optimization: only the previous row is needed, so two 1D arrays (or one with careful in-place updates) reduce space to O(min(m, n)). O(m * n) time.

Complexity

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

Related patterns

  • dynamic-programming
  • string-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google

Practice these live with InterviewChamp.AI

Drill Longest Common Subsequence and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →