🙏

জয়  শ্রী  রাম

🕉

---

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:

• Shortest Common Supersequence
• Interleaving String

Instructor: