Compute longest common subsequence length

Problem

You are given two strings s and t. A subsequence of a string is obtained by deleting zero or more characters without changing the order of the remaining characters.

Return the length of the longest common subsequence (LCS) between s and t.

Input

• Two strings s , t

Output

• An integer: the length of the LCS of s and t

Constraints (typical interview bounds)

• 0 <= len(s), len(t) <= 1000
• Strings contain lowercase/uppercase letters (assume ASCII letters)

Examples

• s = "abcde" , t = "ace" → output 3 (LCS could be "ace" )
• s = "abc" , t = "def" → output 0