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:
- Let m and n be the length of the two strings X and Y.
- If either m or n is 0, then we return 0.
- The problem can be solved using dynamic programming as it satisfies both the properties i.e optimal substructure and overlapping subproblems.
- We create a 2D array DP with size (m+1, n+1) initialized to 0.
- DP[i][j] will store the length of the longest common subsequence for strings X[1…i] and Y[1…j].
- 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]. - 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.
2 comments