Longest common subsequence
Lesson 6 of 15 in Coddy's Dynamic Programming 101 course.
The Longest Common Subsequence (LCS) is a classic computer science problem that involves finding the longest subsequence common to two sequences. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
For example, consider two sequences:
S1 = "AGGTAB"
S2 = "GXTXAYB"
The LCS of S1 and S2 is "GTAB" with a length of 4.
There are several approaches to solve the LCS problem, and the most popular one is the dynamic programming approach.
Challenge
MediumWrite a function that takes two strings as input and returns the length of their longest common subsequence.
Note: This (along with the upcoming algorithms in this course) is considered an advanced algorithm and it might be hard for new programmers to come up with the efficient DP solution by themselves. Don't hesitate to use the hints or the 'Ask AI' button!
Try it yourself
def longest_common_subsequence(str1, str2):
# Write code hereAll lessons in Dynamic Programming 101
3Dynamic programming algorithms
Longest common subsequenceKnapsack problemCoin change problemEdit distance