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.