LCS Reconstruction

mediumBacktrackingStringsdynamic programming

You are given two strings $$$S$$$ and $$$T$$$. Find out one of the Longest Common Subsequences of the two given strings.

A subsequence is a sequence derived from another sequence by deleting some or no elements, while maintaining the original order of the remaining elements.

A common subsequence is a subsequence that appears in both strings.

Input Format:

The first line contains string $$$S$$$ ($$$1 \le |S| \le 3000$$$).

The second line contains string $$$T$$$ ($$$1 \le |T| \le 3000$$$).

$$$S$$$ and $$$T$$$ consist of lower case English letters.

Output Format:

Output a single string representing the Longest Common Subsequence of the two given strings. Multiple LCS answers can exist. You can print any one of them, or -1 if no common subsequence is found.

Examples:

Example 1:

Input:

algopath
pathalzguo

Output:

path

Note:

For the strings algopath and pathalzguo, the longest common subsequence has a length of 4.

One possible answer is path:

  • In algopath, the characters are contiguous.
  • In pathalzguo, the characters are also contiguous.

Another possible answer is algo:

  • In algopath, the characters are contiguous.
  • In pathalzguo, the characters appear in the correct relative order but are not contiguous.

Since multiple answers exist, either path or algo will be accepted as a correct output.

Code

Loading Editor...