You are given strings and
. Find one longest string that is a subsequence of both
and
.
Notes
A subsequence of a string is the string obtained by removing zero or more characters from
and concatenating the remaining characters without changing the order.
Constraints
and
are strings consisting of lowercase English letters.
Input Specification
The first line of input will contain a string .
The second line of input will contain a string .
Output Specification
You are to print out, on a single line, one longest string that is a subsequence of both and
. If there are multiple such strings, any of them will be accepted.
Sample Input 1
axyb
abyxb
Sample Output 1
axb
The answer is axb
or ayb
; either one will be accepted.
Sample Input 2
aa
xayaz
Sample Output 2
aa
Sample Input 3
a
z
Sample Output 3
The answer is (an empty string).
Sample Input 4
abracadabra
avadakedavra
Sample Output 4
aaadara
Comments
Case 105 is a big bully
any advice of the last test case (105)? I got TLE on that one.
Any advice on how to not exceed memory? Do I have to do bottom-up?
You shouldn't store the string for each dp value
Thanks I got it. This should definitely be 10 points ¯\_(ツ)_/¯