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 Sam K., 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

More Dynamic Programming practice problems

See all Dynamic Programming problems →