How do you find the Longest Common Subsequence (LCS) of two strings?

LCS finds the longest sequence present in both strings in the same order (not necessarily contiguous). Use 2D DP table where dp[i][j] = LCS length of first i chars of X and first j chars of Y. If X[i] == Y[j], dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Time and space are O(mn). Backtrack to reconstruct the actual LCS. Used in diff tools and bioinformatics.