Is Longest Common Subsequence easy or hard?

Longest Common Subsequence is generally classified as a medium-level problem. The difficulty comes from defining the correct DP state and recurrence relation, but once the pattern is understood it becomes a standard dynamic programming template for sequence comparison problems.

Longest Common Subsequence Python/Java solution

Python and Java implementations follow the same DP idea: initialize a matrix of size (m+1) x (n+1) and fill it using character comparisons between the two strings. If characters match, add 1 to the diagonal value; otherwise take the maximum from top or left. FleetCode provides full solutions in Python, Java, C++, C#, C, and JavaScript.

How to solve Longest Common Subsequence in O(n)?

Computing the exact LCS for two arbitrary strings requires examining combinations of characters from both strings, which leads to O(m*n) time complexity. The common optimization reduces space to O(min(m,n)) by storing only one DP row, but the time complexity remains O(m*n).

What is the best approach for Longest Common Subsequence?

The most common approach is dynamic programming using a 2D table. Define dp[i][j] as the LCS length for prefixes of the two strings and fill the table using character comparisons. This runs in O(m*n) time and O(m*n) space and is the approach most interviewers expect. A space-optimized version reduces memory to O(min(m,n)).

Is Longest Common Subsequence asked at Google/Amazon/Meta?

Longest Common Subsequence is a classic dynamic programming problem frequently asked in technical interviews at companies such as Google, Amazon, Meta, and Microsoft. It tests understanding of DP state definition, recurrence relations, and optimization techniques.

What data structure is used in Longest Common Subsequence?

The solution primarily uses a dynamic programming table (2D array) to store intermediate LCS lengths for string prefixes. In optimized implementations, a 1D array replaces the full matrix to reduce memory usage while maintaining the same recurrence logic.

What is the time complexity of Longest Common Subsequence?

The standard dynamic programming solution runs in O(m*n) time, where m and n are the lengths of the two input strings. Every pair of characters is compared exactly once while filling the DP table. Space complexity is O(m*n) for the full table or O(min(m,n)) with space optimization.

Description Hints 2 Solution Video 7:55

1143. Longest Common Subsequence

Medium59.6% acceptance19 companies

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.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

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
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

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

Asked at 19 companies

Optum Micro1 Salesforce Bytedance Microsoft Meta Walmart Labs DoorDash ServiceNow Morgan Stanley

Google Amazon

+7 more

Bloomberg Tiktok Visa Accenture

Cisco Apple

TCS

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

Try dynamic programming. DP[i][j] represents the longest common subsequence of text1[0 ... i] & text2[0 ... j].

Hint 2

DP[i][j] = DP[i - 1][j - 1] + 1 , if text1[i] == text2[j] DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) , otherwise

7:55

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution