Longest Common Subsequence
A Classic Dynamic Programming Problem

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
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:
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.