Longest Shared Subsequence
A diff tool compares two strings a and b. A subsequence is what remains after deleting any number of characters without reordering the rest.
Return the length of the longest string that is a subsequence of both a and b.
Example 1
Input: a = "abcde", b = "ace" Output: 3 Explanation: "ace" appears in both.
Example 2
Input: a = "dynamic", b = "program" Output: 2 Explanation: For example "am".
Constraints
- 0 <= a.length, b.length <= 1000
- Strings contain lowercase letters.
Hint 1
Let L[i][j] be the answer for the first i characters of a and the first j of b.
Hint 2
If the last characters match, L[i][j] = L[i-1][j-1] + 1; otherwise it is the larger of L[i-1][j] and L[i][j-1].
Good practice for: Backend Developer, Data Scientist, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Automation Test Engineer, Full Stack Developer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.