Longest Common Subsequence

Problem Given two strings, find the length of their longest common subsequence — the longest sequence of characters appearing in both strings in the same relative order, though not necessarily contiguously. The extended version asks for the subsequence itself, not just its length.

Input / Output

• Input: strings s1 of length m and s2 of length n.
• Output: the LCS length; optionally one actual LCS string.

Constraints

• 1 <= m, n <= 1000 typically, so O(m·n) is the expected complexity.
• Subsequences need not be contiguous — this is not longest common substring.
• The LCS is not unique; any valid one is accepted in the reconstruction variant.

Example

• "abcde", "ace" → 3 ("ace").
• "abc", "def" → 0.
• "aggtab", "gxtxayb" → 4 ("gtab") — the case that punishes greedily taking the first available match.