Solution: Longest Common Subsequence
Understand how to solve the longest common subsequence problem by using dynamic programming and memoization. Explore recursive and optimized approaches, develop skills in reducing time complexity with a 2D table, and learn how to implement these solutions in coding interviews.
Statement
Suppose you are given two strings. You need to find the length of the longest common subsequence between these two strings.
A subsequence is a string formed by removing some characters from the original string while maintaining the relative position of the remaining characters. For example, “abd” is a subsequence of “abcd”, where the removed character is “c”.
If there is no common subsequence, then return 0.
Constraints:
-
str1.length