Another 2D dynamic programming problem, this time with strings. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!
Given two strings, find a longest subsequence common to both strings. Note that unlike substrings, subsequences are not required to be a consecutive section of the original strings.
Your solution should have run-time O($nm$).
Note: There may be multiple subsequences of the same length. You are required to calculate any subsequence of the maximum possible length.
String 1: ABBBAABB String 2: ABBABA
Answer: “ABBBA” (length=5)
String 1: ABACCAA String 2: BAACABAC
Answer: “BACAA” (length=5)
String 1: DBCCBDDACD String 2: CBDCB
Answer: “CBDC” (length=4)
Once you are confidant of your solution, take the quiz! It will provide you with some inputs to run your code on.
Only look at the hints if you can’t solve the problem for at-least 20-minutes. Read only one hint that you could not figure out on your own. Then spend at-least 20-minutes trying to solve the problem again.
Hint 1 (dp state):
lcs(i, j) = length of longest common subsequence of string1[0 … i] and string2[0 … j]
Hint 2 (recursion):
There are two cases:
string1[i] == string2[j] or
string1[i] != string2[j].
string1[i] == string2[j] case is left for you. If
string1[i] != string2[j], then the LCS either does not include
string1[i] or does not include
string2[j]. Hence, lcs(i, j) = max(lcs(i-1, j), lcs(i, j-1)).
Hint 4 (constructing the actual subsequence):
You’ll need to define previous(i, j) to remember the path you took from (0, 0) to (i, j). previous(i, j) should be one of (i-1, j), or (i, j-1) or (i-1, j-1).
The solution for this assignment is included at the end of the quiz.