Skip to main content
Talentd

Longest Common Subsequence - Solution & Explanation

MediumStringDynamic Programming26 min readAsked at: Amazon, Microsoft, Apple +16
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: Given two strings text1 and text2, find the length of their longest common subsequence (LCS). A subsequence keeps the relative order of characters but may skip characters. The task is to determine the maximum number of characters that appear in both strings in the same order.

Approach 1: Dynamic Programming (2D Table) (Time: O(m*n), Space: O(m*n))

The standard solution uses a 2D DP table where dp[i][j] represents the length of the LCS for the prefixes text1[0..i-1] and text2[0..j-1]. Iterate through both strings using nested loops. If the current characters match (text1[i-1] == text2[j-1]), extend the subsequence with dp[i][j] = 1 + dp[i-1][j-1]. If they differ, carry forward the best result from either skipping a character in text1 or text2: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This builds the answer bottom-up while exploring all prefix combinations. The approach is widely used in dynamic programming problems involving strings, especially sequence comparison tasks such as edit distance and diff algorithms.

Approach 2: Optimized Dynamic Programming with Space Reduction (Time: O(m*n), Space: O(min(m,n)))

The 2D DP table only depends on the previous row and the current row. You can reduce memory usage by storing just one row (or two rows) instead of the entire matrix. Iterate through the characters of the first string while updating a 1D array that represents the LCS values for the second string. Track the previous diagonal value (which corresponds to dp[i-1][j-1]) during iteration so you can compute matches correctly. This keeps the same transition logic but compresses the memory footprint significantly. The algorithm still processes every pair of characters, so the time complexity remains O(m*n), but the space drops to O(min(m,n)), which is useful when working with long strings or memory-constrained environments.

Recommended for interviews: Interviewers typically expect the classic 2D dynamic programming formulation first because it clearly demonstrates the recurrence relation and state transition. Once you show the correct DP state definition and transitions, discussing the space optimization shows deeper understanding and practical engineering judgment.

Approach 1: Dynamic Programming Approach

This approach uses dynamic programming to solve the problem by creating a 2D table to store the lengths of the longest common subsequences for different substrings. Each cell dp[i][j] in the table represents the longest common subsequence length of substrings text1[0..i-1] and text2[0..j-1]. The table is filled using the following rules:

  • If the characters text1[i-1] and text2[j-1] are equal, then dp[i][j] = dp[i-1][j-1] + 1.
  • If they are not equal, then dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

The final answer is dp[text1.length][text2.length].

This C solution defines a function longestCommonSubsequence that calculates the longest common subsequence length using a 2D array dp. The program iteratively updates the table based on character matches and topological decision making (max operation). The main function demonstrates this by testing with two example strings and printing the result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), where n and m are the lengths of text1 and text2 respectively.
Space Complexity: O(n*m) for the DP table.

Try this approach in the editor →

Approach 2: Optimized Dynamic Programming with Space Reduction

This optimization reduces space complexity by only storing data for the current and the previous row. The idea remains the same - calculating the LCS length incrementally using a dynamic programming strategy. However, instead of a full 2D table, only two 1D arrays are used, effectively reducing space usage from O(n*m) to O(min(n, m)). This is achieved by noting that each row of the DP table depends only on the previous row. So, we use two arrays that swap every iteration.

The optimized C solution uses two arrays previous and current to store the LCS length for the current and last iteration. After computing each row, the current becomes the previous, thereby saving space. The solution is efficient both in terms of time and space compared to the full 2D table.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), where n is the length of text1 and m is the length of text2.
Space Complexity: O(min(n, m))

Try this approach in the editor →

Approach 3: Dynamic Programming

We define f[i][j] as the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2. Therefore, the answer is f[m][n], where m and n are the lengths of text1 and text2, respectively.

If the ith character of text1 and the jth character of text2 are the same, then f[i][j] = f[i - 1][j - 1] + 1; if the ith character of text1 and the jth character of text2 are different, then f[i][j] = max(f[i - 1][j], f[i][j - 1]). The state transition equation is:

$ f[i][j] = \begin{cases} f[i - 1][j - 1] + 1, & if text1[i - 1] = text2[j - 1] \ max(f[i - 1][j], f[i][j - 1]), & if text1[i - 1] neq text2[j - 1] \end{cases}

The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the lengths of text1 and text2$, respectively.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#Kotlin

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Kotlin

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n*m), where n and m are the lengths of text1 and text2 respectively.
Space Complexity: O(n*m) for the DP table.

Optimized Dynamic Programming with Space Reduction

Time Complexity: O(n*m), where n is the length of text1 and m is the length of text2.
Space Complexity: O(min(n, m))

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (2D Table)O(m*n)O(m*n)General case and easiest way to reason about the LCS recurrence during interviews
Space Optimized Dynamic ProgrammingO(m*n)O(min(m,n))When strings are large and memory usage of the full DP matrix becomes expensive

Video Solution

Longest Common Subsequence • Tushar Roy - Coding Made Simple • 843,231 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Longest Common Subsequence with our built-in code editor and test cases.

Practice on FleetCode
Previous

Delete Operation for Two Strings

Next

Longest Palindromic Subsequence