Problem Description

Given two strings, find the longest common subsequence (LCS). A subsequence is derived by deleting some characters without changing the order of remaining characters. Return the length of the LCS.

Input Format

Two strings on separate lines.

Output Format

Length of the longest common subsequence.

Constraints

• 1 ≤ string length ≤ 1000

• Strings contain only lowercase English letters

• Subsequence maintains relative order

• Use dynamic programming for efficiency

• Return length, not the actual subsequence

Sample Input/Output

Explanation

The longest common subsequence of "abcde" and "ace" is "ace" with length 3.