Find the length of the longest common subsequence (LCS) of two strings.

How to think about it

The phrase that should fire when you hear this one is “longest common thing between two sequences.” LCS, edit distance, longest common substring — they’re the same animal: two strings, and at each character you make a choice (match them, drop the last of one, drop the last of the other). The interviewer is checking whether you can turn that choice into a 2-D table instead of generating all 2^m subsequences and checking each — the brute force that’s exponential and dies on anything real.

Here’s the table. Let dp[i][j] hold the LCS length of the first i characters of text1 and the first j of text2. The whole solution lives in one observation about the last characters. If text1[i-1] and text2[j-1] are the same letter, that letter joins the subsequence, and the rest of the answer is just the LCS of the two prefixes before it — dp[i-1][j-1] + 1. If they differ, that shared letter can’t help, so you throw away one character or the other and keep whichever was longer — max(dp[i-1][j], dp[i][j-1]). Empty strings give 0, which is why row 0 and column 0 stay zero. Fill the grid top-left to bottom-right and the answer waits in the corner.

A worked example

def lcs_length(text1, text2):
    m, n = len(text1), len(text2)
    # (m+1) x (n+1) grid of zeros — the empty-prefix base cases are already set
    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      # both end in the same letter
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # drop one side

    return dp[m][n]

print(lcs_length("abcde", "ace"))       # a, c, e
print(lcs_length("abc", "abc"))         # identical strings
print(lcs_length("abc", "def"))         # nothing in common
print(lcs_length("", "abc"))            # empty string
print(lcs_length("AGGTAB", "GXTXAYB"))  # G, T, A, B

3
3
0
0
4

"abcde" and "ace" share a, c, e in order even though they aren’t next to each other, so the length is 3. Identical strings share everything (3); strings with no common letter share nothing (0); the empty string shares nothing with anyone (0). The last case, 4, is the classic GTAB hidden inside AGGTAB and GXTXAYB — proof that the letters of a subsequence can be scattered far apart.