To kickstart my blog on solving leetcode problems which I deem to be worthy of a writeup (most of them since I usually end up forgetting my approach), let’s look at this classic question. The question asks, given two strings $s$ and $t$, what is the longest subsequence between them?

For our example, let’s use s="abcdef" and b="bcdgf". The longest common subsequence should then be bcdf.

I liken this problem to a Hydra, since it is very easy to get confused by it again even after you solve it.

Examining the problem structure

It does not seem like a greedy two-pointer algorithm is apparent here, since a common subsequence starting with any one common index could possibly stay small until much later on.

We need to find a recurrence relation that will simplify the problem for us:

$$ subseq(s,t) = s[0] + subseq(s[1:], t[1:]), \qquad \text{if } s[0]=t[0] $$ $$ subseq(s,t) = max(subseq(s[1:],t), subseq(s,t[1:])), \qquad \text{ otherwise} $$

The intuition behind this is that we go from left to right parsing both strings. If we see that the start element is the same, we add it to our subsequence. Otherwise, we ignore the first element from both s and t, and we pick whatever residual string gives the largest substring. We then use a dictionary/table so that we can re-use computations to give us a time complexity of $O(M \cdot N)$, where $M,N$ are the lengths of s, t respectively, as opposed to $O(M^{2}\cdot N^{2})$ otherwise.

Example

Solution

Here is the solution code, making use of a memoized DP table.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        
        # Initialize DP table with (m+1) x (n+1) to handle edge cases
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Fill the DP table, iterating backwards from bottom right to top left
        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])
        
        # The length of the longest common subsequence is in dp[0][0]
        return dp[0][0]