1162. Print Longest Common Subsequence

Given two strings a and b, return one longest common subsequence as a string. When multiple exist, return the one obtained by preferring to move up (decrease the index into a) on ties during reconstruction. The input is JSON {a, b}.

Input: JSON {a, b}.

Output: String — a longest common subsequence.

Examples

Input: {"a":"abcde","b":"ace"}
Output: ace
Explanation: The LCS is 'ace'.

Input: {"a":"abc","b":"abc"}
Output: abc
Explanation: Whole string.

Input: {"a":"a","b":"b"}
Output: 
Explanation: Empty LCS.

Constraints

• 0<=|a|,|b|<=1000

Asked by