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!
Problem Statement
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.
Examples
Example 1:
String 1: ABBBAABBString 2: ABBABA
Answer: "ABBBA" (length=5)
Example 2:
String 1: ABACCAAString 2: BAACABAC
Answer: "BACAA" (length=5)
Example 3:
String 1: DBCCBDDACDString 2: CBDCB
Answer: "CBDC" (length=4)
Submitting your solution
Once you are confidant of your solution, take the quiz! It will provide you with some inputs to run your code on.
Progressive 'hint-by-hint' solution
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 3:
Hint 4 (constructing the actual subsequence):
Full solution
The solution for this assignment is included at the end of the quiz.