## 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`

.

- 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. - 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. - 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];
}
};
```