Find the longest sequence two strings share in order. Fill a grid: matching letters extend the diagonal, otherwise take the better neighbour.
▼The problem
LeetCode 1143 (Medium). Given two strings text1 and text2, return the length of their longest common subsequence (letters kept in order, not necessarily adjacent), or 0 if there is none.
Examples: "abcde", "ace" → 3 ("ace"); "abc", "def" → 0.
The solution
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # knot
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]Transcript
Longest Common Subsequence. Given two strings, return the length of the longest subsequence they share: letters kept in order, but not necessarily side by side.
Take A, B, C, D, E and A, C, E. Keep A, C and E from the first, and you get the second one whole: three. But A, B, C and D, E, F share nothing, so that's zero.
The simple way: list every subsequence of one string, and check each against the other. With m letters, that's two to the m subsequences: exponential.
Instead, weave a table. Cell i, j holds the answer for the first i letters of one string and the first j of the other. If their last letters match, tie a knot: one plus the cell up and left. If not, keep the bigger of the cell above and the cell to the left.
In code, make a table of zeros with an extra row and column. Loop over every i and j. On a match, add one to the diagonal. Otherwise, take the max of above and left. Return the bottom right cell.
Let's weave them. Row A: A meets A, a knot: one, and it carries along the row. Row B: no matches, so the ones carry down. Row C: C meets C, one plus one: two. Row D carries the twos. Row E: E meets E, two plus one: three. Follow the knots back: A, C, E.
That's m times n cells, each in constant time: order m times n. Space is the same, but each row only needs the one above it, so two rows are enough.
Match, go diagonal. Miss, take the max. That's Longest Common Subsequence.