# Longest common Subsequence (DP-04)

You are given two strings X and Y of lengths m and n. You need to find the length of the longest common subsequence. A subsequence is a sequence that can be derived from a sequence by deleting some characters from the sequence without changing the order of the characters.

Sample Input: X = “XMJYAUZK”, Y = “MZJAWXU”.
Expected Output: 4
Explanation: The longest common subsequence is “MJAU” of length 4.

Algorithm:

1. Let m and n be the length of the two strings X and Y.
2. If either m or n is 0, then we return 0.
3. The problem can be solved using dynamic programming as it satisfies both the properties i.e optimal substructure and overlapping subproblems.
4. We create a 2D array DP with size (m+1, n+1) initialized to 0.
5. DP[i][j] will store the length of the longest common subsequence for strings X[1…i] and Y[1…j].
6. For every value of i and j, we do the following at every iteration.
If X[i]==Y[j], we set DP[i][j] = DP[i-1][j-1] + 1. This is because if the current characters of both the strings are same we just take the value of longest common subsequence for strings X[1…(i-1)] and Y[1…(j-1)] and increase it by 1.
Else, we find the maximum of longest common subsequences for X[1…i] and Y[1…(j-1)] pair and X[1…(i-1)] and Y[1…j] pair and set the maximum value for DP[i][j].
7. The final answer is stored in DP[m][n]
```#include <bits/stdc++.h>
using namespace std;

int lcs(string X, string Y, int m, int n){

if(m==0 || n==0){
return 0;
}

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(X[j-1]==Y[i-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 X = "XMJYAUZK", Y = "MZJAWXU";
cout<<lcs(X, Y, 8, 7);

return 0;
}```

Also take a look at another popular interview question Longest Common Substring.