Longest Common Subsequence

Given two strings a and b, return the length of their longest common subsequence.

Constraints

• n ≤ 1,000 where n is the length of a
• m ≤ 1,000 where m is the length of b

https://binarysearch.com/problems/Longest-Common-Subsequence

Examples

Example 1

Input

• a = abcvc
• b = bv

Output

• answer = 2

Explanation

bv is the longest common subsequence.

Example 2

Input

• a = abc
• b = abc

Output

• answer = 3

Example 3

Input

• a = abc
• b = def

Output

• answer = 0

Example 4

Input

• a = binarysearch
• b = searchbinary

Output

• answer = 6

Solution