DSA
Longest Common Subsequence
5 approaches incl. Brute Force, Recursive, Memoized DP, and more. Optimal — Time O(m×n), Space O(n).
Practice Link
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.
Brute Force#
Enumerate all subsequences of both strings (2^m and 2^n respectively), then compare every pair to find the longest common one. This is exponential because there are no shared subproblems being leveraged.
- Find all the subsequences of both strings and compare.
O(2^(m + n)) -> TLE (Overlapping subproblems)
Recursive#
The recursive formulation breaks the problem into the last characters of both strings. If text1[m-1] == text2[n-1], they must be part of the LCS — take them and recurse on the remaining prefixes. Otherwise, we try skipping either character and take the better result. This gives an elegant recurrence but recomputes the same (m, n) states many times.
class Solution {
public:
int lcs(string text1, string text2, int m, int n)
{
if(m==0 || n==0)
return 0;
if(text1[m-1] == text2[n-1])
return 1 + lcs(text1, text2, m-1, n-1);
return max(lcs(text1, text2, m-1, n), lcs(text1, text2, m, n-1));
}
int longestCommonSubsequence(string text1, string text2) {
return lcs(text1, text2, text1.size(), text2.size());
}
};
O(2^n) -> TLE (Overlapping subproblems)
Memoized DP Approach#
Cache the result of each (m, n) state in a 2D memo table to avoid recomputation. The recurrence is unchanged from the recursive approach; we simply check the memo table before recursing. This drops the time from O(2^n) to O(m×n) while adding O(m×n) space for the table plus O(n) for the recursion stack.
class Solution {
public:
int lcs(string text1, string text2, int m, int n, vector<vector<int>> &memo)
{
if(m==0 || n==0)
return 0;
if(memo[m][n] != -1)
return memo[m][n];
if(text1[m-1] == text2[n-1])
memo[m][n] = 1 + lcs(text1, text2, m-1, n-1, memo);
else
memo[m][n] = max(lcs(text1, text2, m-1, n, memo), lcs(text1, text2, m, n-1, memo));
return memo[m][n];
}
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> memo(m+1, vector<int>(n+1, -1));
return lcs(text1, text2, m, n, memo);
}
};
Time Complexity: O(m*n)
Space Compelexity: O(m*n) + O(n) -> recursive stack
DP Approach#
Convert the top-down memoized recursion into a bottom-up table. dp[i][j] represents the LCS length for text1[0..i-1] and text2[0..j-1]. Fill row by row, left to right — each cell only depends on the cell diagonally above-left (dp[i-1][j-1]) or one of the cells directly above/left. The answer is dp[m][n].
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(text1[i-1] == text2[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}
};
Time Complexity: O(m*n)
Space Compelexity: O(m*n)
Space Optimized Tabulation#
Since each row of the DP table only depends on the previous row, we can keep just two 1D arrays (prev and curr) instead of the full m×n matrix. After processing each row, swap curr into prev. This reduces space from O(m×n) to O(n) with the same O(m×n) time.
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<int> prev(n+1, 0);
vector<int> curr(n+1, 0);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(text1[i-1] == text2[j-1])
curr[j] = 1 + prev[j-1];
else
curr[j] = max(prev[j], curr[j-1]);
}
prev = curr;
}
return prev[n];
}
};
Time Complexity: O(m*n)
Space Compelexity: O(n)
Follow Up: Build the LCS sequence#
#include <vector>
using namespace std;
vector<char> longestCommonSubsequence(string str1, string str2) {
int m = str1.size();
int n = str2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(str1[i-1] == str2[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
int i = m, j = n;
vector<char> lcs;
while(i>0 && j>0){
if(str1[i-1] == str2[j-1])
{
lcs.push_back(str1[i-1]);
i--;
j--;
} else if(dp[i-1][j] > dp[i][j-1]){
i--;
}else {
j--;
}
}
reverse(lcs.begin(), lcs.end());
return lcs;
}
Time Complexity: O(m×n)+O(m+n)=O(m×n)
- O(m*n) -> for creating the lcs DP table
- O(m+n) -> for building the sequence