Longest Common Subsequence
InterviewTime limit0.1sMemory limit256 MB
Compute the length of the longest subsequence shared by two uppercase strings of length up to 1000.
- Level
Medium4 of 10
- Topics
- Dynamic programming
- Solved
- No attempts yet
Problem
Delete zero or more elements from a sequence and keep the remaining elements in their original order. What is left is a subsequence of the original. A sequence that is a subsequence of both of two given sequences is a common subsequence of the two.
The LCS (Longest Common Subsequence) problem asks for the longest common subsequence of two given sequences. For example, the LCS of ACAYKP and CAPCAK is ACAK, which has length 4.
Input
The first line and the second line each contain one string. Both strings consist only of uppercase letters, and each is at most 1000 characters long.
Output
Print the length of the LCS of the two strings on the first line. If the two strings have no character in common, print 0.