Back to solutions

Longest Common Subsequence

MediumDynamic Programming

Return the length of the longest subsequence common to two strings.

Open problem
Constraints
  • 1 <= text1.length, text2.length <= 1000

2D DP over prefixes

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

dp[i][j] is the LCS of the first i and j characters. If the characters match, extend the diagonal; otherwise take the better of dropping one character from either string.

#include <bits/stdc++.h>
using namespace std;

int longestCommonSubsequence(string a, string b) {
    int n = a.size(), m = b.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++)
            dp[i][j] = a[i-1] == b[j-1] ? dp[i-1][j-1] + 1
                                        : max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}