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.