Longest Common Subsequence
Return the length of the longest subsequence common to two strings. A subsequence keeps order but may skip characters.
A way to picture it
Two friends each describe their day as a string of events. The longest common subsequence is the longest story they both lived through in the same order, skipping anything only one of them did.
How to approach it
dp[i][j] = LCS of the first i letters and the first j letters. On a match, dp[i−1][j−1] + 1; otherwise max(dp[i−1][j], dp[i][j−1]).
Example
Input: {"text1":"abcde","text2":"ace"}. Output: 3.
Complexity: O(m · n) time and O(m · n) space. One constant-time cell per pair of prefixes.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.