1143. Longest Common Subsequence Solution

Q: 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.

Q: 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.

Q: 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).

Q: 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)).

Q: 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.

Q: 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.

Q: 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.

The 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.

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].

Python

def longest_common_subsequence(text1, text2):
    n, m = len(text1), len(text2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            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[n][m]

print(longest_common_subsequence("abcde", "ace"))

Java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        return dp[n][m];
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size();
    int m = text2.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            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[n][m];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

JavaScript

function longestCommonSubsequence(text1, text2) {
    const n = text1.length;
    const m = text2.length;
    const dp = Array.from({length: n + 1}, () => Array(m + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][m];
}

console.log(longestCommonSubsequence("abcde", "ace"));

#include <stdio.h>
#include <string.h>

int longestCommonSubsequence(char* text1, char* text2) {
    int n = strlen(text1);
    int m = strlen(text2);
    int dp[n+1][m+1];
    memset(dp, 0, sizeof(dp));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (text1[i-1] == text2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1];
        }
    }
    
    return dp[n][m];
}

int main() {
    char text1[] = "abcde";
    char text2[] = "ace";
    printf("%d\n", longestCommonSubsequence(text1, text2));
    return 0;
}

using System;

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int n = text1.Length;
        int m = text2.Length;
        int[,] dp = new int[n + 1, m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1])
                    dp[i, j] = dp[i - 1, j - 1] + 1;
                else
                    dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }

        return dp[n, m];
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.LongestCommonSubsequence("abcde", "ace"));
    }
}

This Python solution defines a function longest_common_subsequence which calculates the LCS using a dynamic programming table dp. Each entry in dp is filled based on the character comparison and prior calculated results for subsequences.

Complexity

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

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.

Python

def longest_common_subsequence(text1, text2):
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    n, m = len(text1), len(text2)

    previous = [0] * (m + 1)
    current = [0] * (m + 1)

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i - 1] == text2[j - 1]:
                current[j] = previous[j - 1] + 1
            else:
                current[j] = max(previous[j], current[j - 1])
        previous, current = current, previous

    return previous[m]

print(longest_common_subsequence("abcde", "ace"))

Java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        if (n < m) {
            String temp = text1;
            text1 = text2;
            text2 = temp;
            n = text1.length();
            m = text2.length();
        }
        int[] previous = new int[m + 1];
        int[] current = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1))
                    current[j] = previous[j-1] + 1;
                else
                    current[j] = Math.max(previous[j], current[j-1]);
            }
            int[] temp = previous;
            previous = current;
            current = temp;
        }
        return previous[m];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.longestCommonSubsequence("abcde", "ace"));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestCommonSubsequence(string text1, string text2) {
    int n = text1.size();
    int m = text2.size();
    if (n < m) {
        swap(text1, text2);
        swap(n, m);
    }
    vector<int> previous(m + 1, 0);
    vector<int> current(m + 1, 0);

    for (int i = 1; i <= n; i++) {
        fill(current.begin(), current.end(), 0);
        for (int j = 1; j <= m; j++) {
            if (text1[i-1] == text2[j-1])
                current[j] = previous[j-1] + 1;
            else
                current[j] = max(previous[j], current[j-1]);
        }
        swap(previous, current);
    }
    return previous[m];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << longestCommonSubsequence(text1, text2) << endl;
    return 0;
}

JavaScript

function longestCommonSubsequence(text1, text2) {
    if (text1.length < text2.length) {
        [text1, text2] = [text2, text1];
    }
    const n = text1.length;
    const m = text2.length;

    let previous = Array(m + 1).fill(0);
    let current = Array(m + 1).fill(0);

    for (let i = 1; i <= n; i++) {
        current.fill(0);
        for (let j = 1; j <= m; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                current[j] = previous[j - 1] + 1;
            } else {
                current[j] = Math.max(previous[j], current[j - 1]);
            }
        }
        [previous, current] = [current, previous];
    }

    return previous[m];
}

console.log(longestCommonSubsequence("abcde", "ace"));

#include <stdio.h>
#include <string.h>

int longestCommonSubsequence(char* text1, char* text2) {
    int n = strlen(text1);
    int m = strlen(text2);
    if (n < m) {
        return longestCommonSubsequence(text2, text1);
    }
    int previous[m + 1];
    int current[m + 1];
    memset(previous, 0, sizeof(previous));

    for (int i = 1; i <= n; i++) {
        memset(current, 0, sizeof(current));
        for (int j = 1; j <= m; j++) {
            if (text1[i-1] == text2[j-1])
                current[j] = previous[j-1] + 1;
            else
                current[j] = (previous[j] > current[j-1]) ? previous[j] : current[j-1];
        }
        memcpy(previous, current, sizeof(current));
    }
    return previous[m];
}

int main() {
    char text1[] = "abcde";
    char text2[] = "ace";
    printf("%d\n", longestCommonSubsequence(text1, text2));
    return 0;
}

using System;

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int n = text1.Length;
        int m = text2.Length;
        if (n < m) {
            var tempStr = text1;
            text1 = text2;
            text2 = tempStr;
            n = text1.Length;
            m = text2.Length;
        }
        int[] previous = new int[m + 1];
        int[] current = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1[i - 1] == text2[j - 1])
                    current[j] = previous[j - 1] + 1;
                else
                    current[j] = Math.Max(previous[j], current[j - 1]);
            }
            var temp = previous;
            previous = current;
            current = temp;
        }
        return previous[m];
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.LongestCommonSubsequence("abcde", "ace"));
    }
}

This Python solution efficiently reduces space usage by keeping data for the previous and the current row only, effectively moving the comparison outcome and using list swapping. This process is consistent with the previous solutions while being concise in Python.

Complexity

Time Complexity: O(n*m)
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.

TypeScript

function longestCommonSubsequence(text1: string, text2: string): number {
    const m = text1.length;
    const n = text2.length;
    const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
    return f[m][n];
}

func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	f := make([][]int, m+1)
	for i := range f {
		f[i] = make([]int, n+1)
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				f[i][j] = f[i-1][j-1] + 1
			} else {
				f[i][j] = max(f[i-1][j], f[i][j-1])
			}
		}
	}
	return f[m][n]
}

Kotlin

class Solution {
    fun longestCommonSubsequence(text1: String, text2: String): Int {
        val m = text1.length
        val n = text2.length
        val f = Array(m + 1) { IntArray(n + 1) }
        for (i in 1..m) {
            for (j in 1..n) {
                if (text1[i - 1] == text2[j - 1]) {
                    f[i][j] = f[i - 1][j - 1] + 1
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1])
                }
            }
        }
        return f[m][n]
    }
}

Rust

impl Solution {
    pub fn longest_common_subsequence(text1: String, text2: String) -> i32 {
        let (m, n) = (text1.len(), text2.len());
        let (text1, text2) = (text1.as_bytes(), text2.as_bytes());
        let mut f = vec![vec![0; n + 1]; m + 1];
        for i in 1..=m {
            for j in 1..=n {
                f[i][j] = if text1[i - 1] == text2[j - 1] {
                    f[i - 1][j - 1] + 1
                } else {
                    f[i - 1][j].max(f[i][j - 1])
                };
            }
        }
        f[m][n]
    }
}

Try this approach in the editor

Complexity comparison

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

Complexity analysis

Approach	Time	Space	When 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 Programming	O(m*n)	O(min(m,n))	When strings are large and memory usage of the full DP matrix becomes expensive

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.

Longest Common Subsequence solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Optimized Dynamic Programming with Space Reduction

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Common Subsequence solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Optimized Dynamic Programming with Space Reduction

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems