Longest Common Subsequence
A Classic Dynamic Programming Problem

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
Given two sequences, find the length of longest subsequence present in both of them.A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.
Solution:
We can start comparing either from the beginning of the two strings or from the end. Whichever way we choose, the overall algorithm will remain the same.For our solution let's compare the end characters of the two given strings.
Suppose we are given two strings str1 and str2. str1 has length len1 and str2 has length len2. Say
dp[i][j]
gives the Longest Common Subsequence of the first i
characters of str1 and first j
characters of str2.
At any point of time, we would have one of these two situations:

str1.charAt(len1  1) == str2.charAt(len2  1)
In this case, since the character at index (len1  1) of str1 and character at (len2  1) are the same we can definitely include one instance of the character in the Longest Common Subsequence, and then prepend whatever is the result for the rest of str1 and str2, i.e,dp[len1  1][len2  1]
.
So,dp[len1][len2] = dp[len1  1][len2  1] + str1.charAt(len1  1)
If we are interested in computing (in that case dp[len1][len2] will represent length of the Longest Common Subsequence of the firstlen1
characters of str1 and firstlen2
characters of str2 ) only the length of the Longest Common Subsequence then we have:
dp[len1][len2] = dp[len1  1][len2  1] + 1

str1.charAt(len1  1) != str2.charAt(len2  1)
In this case we need to see which one gives more optimal result:dp[len1  1][len2]
ordp[len1][len2  1]
.
dp[len1][len2] = max(dp[len1  1][len2], dp[len1][len2  1])
If we are interested in computing (in that case dp[len1][len2] will represent length of the Longest Common Subsequence of the firstlen1
characters of str1 and firstlen2
characters of str2 ) only the length of the Longest Common Subsequence then we have:
dp[len1][len2] = max(dp[len1  1][len2], dp[len1][len2  1])
The below code implements the above thought process in bottomup tabulation process:
public String findLCS(String str1, String str2)
{
int len1 = str1.length();
int len2 = str2.length();
String[][] dp = new String[len1+1][len2+1];
for(int i=0;i<=len1;++i) {
for(int j=0;j<=len2;++j)
{
if(i==0  j==0) { // if we are taking zero length of any string then LCS will be empty string
dp[i][j] = "";
}
else if(str1.charAt(i1) == str2.charAt(j1)) {
dp[i][j] = dp[i1][j1] + str1.charAt(i1);
}
else {
dp[i][j] = dp[i][j1].length() > dp[i1][j].length() ? dp[i][j1] : dp[i1][j];
}
}
}
return dp[len1][len2];
}
The below code computes the length of the Longest Common Subsequence:
public int findLcsLength(String str1, String str2)
{
int len1 = str1.length();
int len2 = str2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=0;i<=len1;++i) {
for(int j=0;j<=len2;++j)
{
if(i==0  j==0) { // if we are taking zero length of any string then length of LCS will be zero
dp[i][j] = 0;
}
else if(str1.charAt(i1) == str2.charAt(j1)) {
dp[i][j] = dp[i1][j1] + 1;
}
else {
dp[i][j] = Math.max(dp[i][j1], dp[i1][j]);
}
}
}
return dp[len1][len2];
}
Applications of Longest Common Subsequence Approach:
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn