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:



Login to Access Content



Python Solution:



Login to Access Content




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

Java Code:



Login to Access Content



Python Code:



Login to Access Content




Applications of Longest Common Subsequence Approach:



Instructor:



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



Help Your Friends save 40% on our products

wave