Longest Common Subsequence: The Grid That Explains Diffs

"Longest Common Subsequence" is a Medium-level staple in Amazon, Google, Microsoft loops, and it is a textbook fit for the Dynamic Programming pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 8 of 11 in the Dynamic Programming arc.

The Problem

Given two strings, return the length of their longest common subsequence — characters in order, not necessarily contiguous. The foundational two-sequence DP: the machinery under diff tools, DNA alignment, and half the hard string questions on every list.

Input:  text1 = "abcde", text2 = "ace"
Output: 3

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Two sequences compared by prefixes is a 2D table by construction: dp[i][j] for prefixes of lengths i and j. Matching last characters extend the diagonal; otherwise inherit the better of dropping one character from either side. Any 'align two sequences' phrasing compiles to this.

The Approach

Fill the (m+1) x (n+1) table with the empty-prefix row and column at zero — the padding that eliminates every boundary special case. Row-major fill, two-case recurrence, answer in the corner.

Only the previous row is ever read, so memory drops to O(n) with a rolling row — mention it, and note that recovering the actual subsequence needs the full table walked backwards. Choosing which to implement based on what is asked for is the judgment being graded.

Python Solution

def longest_common_subsequence(text1: str, text2: str) -> int:
    """Length of the LCS of two strings."""
    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        # extend the match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Complexity

• Time: O(m·n) — one constant-time cell fill per prefix pair
• Space: O(m·n) — the full table (O(min(m, n)) with rolling rows)

Interview Tips and Follow-Ups

• The one-based padding trick (indices shifted by one) is what keeps the code branch-free — explain it rather than letting it look accidental.
• Edit Distance (this arc's finale) is this table with a third option per cell — presenting LCS first makes Edit Distance a delta, not a new problem.
• Delete Operation for Two Strings and Minimum ASCII Delete are direct LCS corollaries — m + n − 2·LCS and friends. Cheap wins if named.

That wraps part 8 of the Dynamic Programming arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.