Longest Common Subsequence

Problem: Given two strings, find the length (or the actual subsequence) of their longest common subsequence (LCS) -- a sequence that appears in both strings in the same relative order, but not necessarily contiguously.

Constraints: Strings can contain any characters; subsequence need not be contiguous.

Example: Input: "abcde", "ace" -> Output: 3 ("ace").

Approach: Classic 2D DP: dp[i][j] = LCS length of the first i chars of string1 and first j chars of string2. If characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). O(m*n) time and space (reducible to O(min(m,n)) space).