Given two strings text1 and text2, return the length of their longest common subsequence — characters that appear in both, in the same relative order, but not necessarily contiguous.
Example
Input text1 = "abcde", text2 = "ace"
Output 3
Key Pointers
When the current characters of both strings match, the subsequence grows by one from the subproblem where both strings advance past that character.
When they don't match, the best answer is whichever subproblem is better: dropping a character from the first string, or from the second.
A 2D grid where each cell answers "LCS of these two suffixes" avoids recomputing the same suffix pair twice.
Step-by-Step Analysis
Create a grid sized (len(text1)+1) × (len(text2)+1), filled with 0 — the extra row/column represent an empty string.
Walk both strings from the end backward toward the start.
If the characters at the current positions match, the cell takes 1 plus the diagonal cell (both strings advanced together).
Otherwise, the cell takes the better of the cell to the right or the cell below (dropping one character from either string).
The top-left cell holds the answer for the full strings.
Complexity
Time: O(m · n) — Space: O(m · n)
Code
def longestCommonSubsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
return dp[0][0]
Code Explanation
How the solution above works, piece by piece.
dp[i][j] = length of the LCS of the suffixes text1[i:] and text2[j:]. The extra last row and column (empty suffix) are 0.
Fill from the bottom-right so the cells each entry depends on are already known.
If text1[i] == text2[j], that letter can be part of the subsequence: 1 + dp[i+1][j+1].
Otherwise one of the two letters is not used: take the better of skipping it in text1 (dp[i+1][j]) or in text2 (dp[i][j+1]).
dp[0][0] is the answer. O(m × n) time and space.
Visual Walkthrough
Running it on text1 = "abcde", text2 = "ace":
The table is filled from the bottom-right corner. When the two letters match, that match plus the best for the rest (diagonal) is taken; otherwise the better of skipping one letter from either string. The matches a, c, e give length 3.