Longest Common Subsequence

Medium

dynamic-programmingstring

Given strings text1 and text2, return the length of their longest common subsequence (characters in order, not necessarily contiguous); 0 if none.

Input

Line 1: string text1
Line 2: string text2

Output: the LCS length.

Example 1

Input:

abcde
ace

Output:

"ace".

Example 2

Input:

abc
def

Output:

Constraints

1 ≤ lengths ≤ 1000
Lowercase English letters.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Longest Common Subsequence

Medium

dynamic-programmingstring

Given strings text1 and text2, return the length of their longest common subsequence (characters in order, not necessarily contiguous); 0 if none.

Input

Line 1: string text1
Line 2: string text2

Output: the LCS length.

Example 1

Input:

abcde
ace

Output:

"ace".

Example 2

Input:

abc
def

Output:

Constraints

1 ≤ lengths ≤ 1000
Lowercase English letters.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.