Longest Common Subsequence

Problem

Given two strings text1 and text2, return the length of the longest string that appears as a subsequence of both. A subsequence keeps characters in their original order but may skip any number of them. If the strings share no characters, return 0.

• Each string can run up to a few thousand characters.
• Both strings contain only lowercase English letters.

Examples

• text1 = "pumpkin", text2 = "pudding" → 4, via the subsequence "puin".
• text1 = "flag", text2 = "flags" → 4, since "flag" itself is a subsequence of "flags".
• text1 = "cat", text2 = "dog" → 0. No character is shared at all.

Hints

1. Compare the last characters of the two strings. What can you conclude if they match? What if they do not?
2. The answer for a pair of prefixes depends only on answers for shorter prefixes. Which three?
3. Classic 2D DP over prefix lengths: dp[i][j] for text1[:i] and text2[:j].