Given two strings X and Y, write a program to return the length of their longest common subsequence.

Problem Note

• A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "prt" is a subsequence of "pqrst" while "ptr" is not).
• A common subsequence of two strings is a subsequence that is common to both strings.
• If there is no common subsequence, return 0.
• The input strings consist of lowercase English characters only.

Example 1

Input: X = "pqrst", Y = "prt" 
Output: 3  
Explanation: The longest common subsequence is "prt" and its length is 3.

Example 2

Input: X = "pqr", Y = "pqr"
Output: 3
Explanation: The longest common subsequence is "pqr" and its length is 3.

Example 3

Input: X = "pqr", Y = "stu"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.