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: ABBBAABBString 2: ABBABA
Answer: "ABBBA" (length=5)
String 1: ABACCAAString 2: BAACABAC
Answer: "BACAA" (length=5)
String 1: DBCCBDDACDString 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):
Hint 2 (recursion):
Hint 4 (constructing the actual subsequence):
The solution for this assignment is included at the end of the quiz.