LCS of Three Strings
InterviewTime limit2sMemory limit128 MB
Compute the length of the longest common subsequence shared by three given strings using dynamic programming.
- Level
Medium4 of 10
- Topics
- Dynamic programming, String
- Solved
- No attempts yet
Problem
Given three strings, find the length of the longest subsequence that appears in all three strings.
A subsequence is obtained by deleting zero or more characters from a string while preserving the relative order of the remaining characters.
Input
The first line contains the first string, the second line contains the second string, and the third line contains the third string.
All three strings consist only of lowercase English letters, and each string has length at most 100.
Output
Print the length of the LCS of the three strings on the first line.