## Problem

Problem ID: 1143

Title: Longest Common Subsequence

Description: Given two strings, find the length of the longest common subsequence.

## Thoughts

The first thing that came to my mind after reading this question is DP as it involved comparing 2 different strings. However, I was having trouble with deriving the DP state transition as it involved.

My initial approach was to store a 4D DP where `DP[i_l][i_r][j_l][j_r]` will store the longest length for `text1[i_l][i_r]` and `text[j_l][j_r]` but this would result in TLE as `text1.length < 1000` and the total run time would be `O(n^4) = 1e12`. I soon realise that we should greedily add characters to the subsequence and there is no need to store the left bound in the DP which would reduce the complexity to `O(n^2)`.

## Solution

### Explanation

General Idea: Lets say you are currently at index `i` and `j` of `text1` and `text2`. There are three scenario you should consider to calculate the longest subsequence up till `i` and `j`.

1. What is the longest subsequence up till `i-1` and `j`. The similarity of characters `text1[i]` and `text2[j]` will not contribute to longest subsequence as `text2[j]` has already been used.
2. What is the longest subsequence up till `i` and `j-1`. The similarity of characters `text1[i]` and `text2[j]` will not contribute to longest subsequence as `text1[i]` has already been used.
3. What is the longest subsequence up till `i-1` and `j-1`. The similarity of `text1[i]` and `text2[j]` can contribute to the longest subsequence.

Using this idea we can formulate the following DP transition.

DP

`DP[i][j]`: stores the longest subsequence for the first `i` characters of `text1` and first `j` characters of `text2`. Even though I prefer to use index of characters instead of length for DP parameters, I use length for this problem to allow us to not check for index in range.

DP transition: `DP[i][j] = max(DP[i-1][j-1], DP[i][j-1], DP[i-1][j-1] + text1[i-1] == text2[j-1] ? 1 : 0)`

Implementation

``````class Solution {
public:
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++) {
char c1 = text1[i - 1];
char c2 = text2[j - 1];
int exclude_curr = max(dp[i-1][j], dp[i][j-1]);
int curr_take = dp[i-1][j-1];
if (c1 == c2) curr_take++;
dp[i][j] = max(curr_take, exclude_curr);
}
}
return dp[n][m];
}
};
``````