4.24.2 — Longest Common Subsequence

LeetCode 1143 · Medium · ★ Blind 75

The problem

Return the length of the longest subsequence common to both strings. A subsequence keeps order but may skip characters.

"abcde", "ace"   →  3     ("ace")
"abc",   "abc"   →  3
"abc",   "def"   →  0

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

Plain-English Restatement: Given two strings, you want to find the longest sequence of characters that appears in both strings in the exact same order. The characters do not need to be consecutive. Think of it like taking both strings and erasing some letters from each until what's left is identical, trying to erase as few letters as possible.

Brute Force Approach: The naive approach is to generate all possible subsequences of text1 and check if they exist in text2, keeping track of the longest one.

• Time Complexity: O(n \cdot 2^m). A string of length m has 2^m possible subsequences. Checking each subsequence against the other string takes O(n) time. For strings of length 1000, 2^{1000} is unfathomably large.
• Why it's wasteful: Generating all combinations throws away a lot of overlap. If we already know that "ab" matches with "ab", adding "c" to both just extends the known match. DP allows us to build the answer incrementally character-by-character.

The pattern

This is the template for every "compare two sequences" problem, so it is worth learning properly rather than memorising.

Whenever a problem involves two strings, make a grid: one axis per string. That single decision is the whole recognition step.

Let dp[i][j] be the LCS length of the first i characters of text1 and the first j of text2.

Now compare the two characters at the end of those prefixes. There are exactly two cases:

They match. That character can be the end of the common subsequence, so take it and shrink both:

dp[i][j] = 1 + dp[i-1][j-1]

They differ. They cannot both be the ending, so at least one of them is not used. Try dropping each and keep the better:

dp[i][j] = \max\big(dp[i-1][j],\ dp[i][j-1]\big)

Base case: dp[0][j] = dp[i][0] = 0. An empty string shares nothing.

Why "prefixes" and not "ending at". Using prefix lengths means the answer is dp[m][n] directly, and the empty prefixes give the base row and column for free.

ELI5 Analogy: Imagine you have two lines of kids arranged by height, and you want to pull out the longest possible pair of identical lines. You look at the last kid in both lines. If they are wearing the exact same shirt (a match!), you pull them out, tell them to hold hands, and repeat the process for the remaining kids. If they are wearing different shirts (a mismatch!), they can't both be at the end of your matched line. You have to try sending one of them away, and then try sending the other one away, and see which option leaves you with a better matched line overall.

The solution

Python

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)]      # note: m+1 by n+1

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:        # note the −1 offsets
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]

TypeScript

function longestCommonSubsequence(text1: string, text2: string): number {
  const m = text1.length, n = text2.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }

  return dp[m][n];
}

The (m+1) × (n+1) table and the −1 offsets go together. Row i means "the first i characters", so row 0 is the empty prefix and the character it just consumed is text1[i-1]. Sizing the table m × n instead forces a special case for the first row and column, and it is where most of the errors in this family come from.

Fill order: dp[i][j] reads [i-1][j-1], [i-1][j] and [i][j-1] — all smaller. Top to bottom, left to right.

Trace

"abcde" against "ace":

        ''  a  c  e
   ''    0  0  0  0
    a    0  1  1  1
    b    0  1  1  1
    c    0  1  2  2
    d    0  1  2  2
    e    0  1  2  3

Read the diagonal jumps: a matches at (1,1), c at (3,2), e at (5,3). The answer 3 is in the bottom-right corner.

Space optimisation

The recurrence only ever reads the previous row and the current one, so two rows suffice:

prev = [0] * (n + 1)
for i in range(1, m + 1):
    curr = [0] * (n + 1)
    for j in range(1, n + 1):
        if text1[i-1] == text2[j-1]:
            curr[j] = 1 + prev[j-1]
        else:
            curr[j] = max(prev[j], curr[j-1])
    prev = curr
return prev[n]

O(\min(m, n)) space if you also make the shorter string the inner axis.

But if you need the subsequence itself, keep the full table and walk backwards from dp[m][n]: a diagonal step means the character was matched, otherwise move towards the larger neighbour. Reconstruction always needs the table — the same trade as in 4.23.

Complexity

O(mn) time, O(mn) or O(n) space.

Code Walkthrough

1. Grid Setup: dp = [[0] * (n + 1) for _ in range(m + 1)] creates a matrix with an extra row and column filled with 0s. This elegantly handles our base cases (comparing against an empty string always yields 0 matches).
2. Double Loop: We iterate through all combinations of prefixes from 1 to m and 1 to n.
3. The Offset: text1[i - 1] == text2[j - 1]. Because our DP table is 1-indexed (index 1 means a prefix of length 1), we map i=1 to the 0th character of the string.
4. The Match: dp[i][j] = 1 + dp[i - 1][j - 1]. If the letters match, the LCS length is 1 plus whatever the LCS was before we included these two letters (the diagonal cell up and left).
5. The Mismatch: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]). If they don't match, the current LCS is the best we could do by ignoring the current letter of text1 (cell directly above) OR ignoring the current letter of text2 (cell directly left).

Complexity Derivation

• Time Complexity: O(m \times n). We fill out a 2D matrix of size (m+1) \times (n+1). Inside the inner loop, we perform O(1) operations (a simple equality check and a max() or addition). Thus, total time is proportional to the number of cells.
• Space Complexity: O(m \times n) for the full 2D table, because we store an integer for every pair of prefix lengths. If we apply the space optimization mentioned above, it drops to O(\min(m, n)) because we only ever keep two rows in memory at any time.

Edge Cases

• No common characters: e.g., "abc" and "def". The else branch will always trigger, carrying 0s all the way through the table. Returns 0.
• One string is empty: Not possible given constraints length >= 1, but if it were, the extra 0 row/column handles it perfectly.

The family this template solves

Almost every two-string DP is this grid with the two cases rewritten:

problem	match case	mismatch case
LCS	1 + dp[i-1][j-1]	max(dp[i-1][j], dp[i][j-1])
Edit Distance	dp[i-1][j-1]	1 + min of three
Distinct Subsequences	dp[i-1][j-1] + dp[i-1][j]	dp[i-1][j]
Longest Common Substring	1 + dp[i-1][j-1]	0 — must be contiguous
Shortest Common Supersequence	1 + dp[i-1][j-1]	1 + min(dp[i-1][j], dp[i][j-1])

Longest Common Substring differs by one cell: a mismatch resets to 0, because a substring must be contiguous. And the answer is the maximum over the table rather than the corner, since the best run may end anywhere.

Two other useful facts:

• Longest Palindromic Subsequence of s = LCS of s and s reversed.
• Minimum deletions to make two strings equal = m + n − 2 × LCS.

Where this goes next

• Edit Distance — the same grid with three operations. 4.24.9.
• Distinct Subsequences — counting instead of measuring. 4.24.8.
• Interleaving String — two strings against a third. 4.24.6.
• diff — the Unix tool is LCS on lines instead of characters. Git's diff is a tuned version of the same algorithm, which is a good thing to mention.

What the interviewer will push on

"Why a 2-D table?" Two sequences, one axis each. Say it as the recognition step.

"Derive the two cases." Characters match or they do not; if they differ, at least one is unused.

"Why is the table (m+1) × (n+1)?" The empty prefixes give the base row and column with no special case.

"Can you use O(n) space?" Two rows — but you lose the ability to reconstruct the subsequence.

"How do you get the subsequence itself?" Walk the full table backwards.

"What changes for the longest common substring?" A mismatch resets the cell to 0, and the answer is the table maximum.

One thing to volunteer: mention that this is what diff does. It turns an exercise into a tool you use every day, and it makes the problem memorable.

Next: 4.24.3 Best Time to Buy and Sell Stock with Cooldown — where the second dimension is not a position but a state.