Longest Common Subsequence

Intuition

Let dp[i][j] be the length of the longest common subsequence of the first i characters of text1 and the first j characters of text2. If either prefix is empty the answer is 0, which is why the top row and left column stay zero and need no special handling. When the current characters text1[i-1] and text2[j-1] match, that shared character can extend the best subsequence of the smaller prefixes, giving dp[i][j] = dp[i-1][j-1] + 1. When they do not match, the best we can do is drop one of the two characters, so dp[i][j] is the larger of dp[i-1][j] and dp[i][j-1]. Processing rows and columns in increasing order means every value we read has already been finalized, and dp[m][n] holds the final answer.

Algorithm walkthrough

1. 1Create a grid of size (m + 1) by (n + 1) initialized to zero, so the empty-prefix base cases are already handled.
2. 2Loop i from 1 to m and j from 1 to n to consider each pair of prefixes.
3. 3When text1[i-1] equals text2[j-1], set dp[i][j] to dp[i-1][j-1] + 1 to include the shared character.
4. 4When the characters differ, take the maximum of dp[i-1][j] and dp[i][j-1] to drop one character.
5. 5Continue until the entire grid is populated in order.
6. 6Return dp[m][n], the length of the longest common subsequence of the full strings.

Implementation

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        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
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[m][n]