• 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.



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 first len1 characters of str1 and first len2 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] or dp[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 first len1 characters of str1 and first len2 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 bottom-up tabulation process:

Java Solution:



This is a Premium Content.
Please subscribe to Algorithms course to access the solution.




Python Solution:



This is a Premium Content.
Please subscribe to Algorithms course to access the solution.





The below code computes the length of the Longest Common Subsequence:

Java Code:



This is a Premium Content.
Please subscribe to Algorithms course to access the solution.




Python Code:



This is a Premium Content.
Please subscribe to Algorithms course to access the solution.





Applications of Longest Common Subsequence Approach:



The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave